Submission #1303304

#TimeUsernameProblemLanguageResultExecution timeMemory
1303304zbyszkoBosses (BOI16_bosses)C++20
67 / 100
1594 ms896 KiB
#include <bits/stdc++.h> using namespace std; using ull = unsigned long long; using ll = long long; #define x first #define y second vector<vector<int>> adj; ll bdfs(int f,int n){ vector<vector<int>> ch(n+1); vector<bool> visit(n+1,false); int used=0; queue<int> q; q.push(f); visit[f]=true; used++; int v; while(!q.empty()){ v=q.front(); q.pop(); for(int c:adj[v]){ if(!visit[c]){ visit[c]=true; ch[v].push_back(c); used++; q.push(c); } } } if(used<n){ return LLONG_MAX; } visit.assign(n+1,false); vector<int> dp(n+1,0); ll sum=0; stack<tuple<int,int,bool>> s; s.push({f,-1,0}); visit[f]=true; while(!s.empty()){ auto [v,p,st]=s.top(); s.pop(); if(st==0){ s.push({v,p,1}); for(int c:ch[v]){ if(c==p) continue; if(!visit[c]){ visit[c]=true; s.push({c,v,0}); } } } else{ dp[v]=1; for(int c:ch[v]){ if(c!=p){ dp[v]+=dp[c]; } } sum+=dp[v]; } } return sum; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n;cin >> n; adj.resize(n+1); for(int i=1,k;i<=n;i++){ cin >> k; for(int j=0,v;j<k;j++){ cin >> v; adj[v].push_back(i); } } ll sum=LLONG_MAX; for(int i=1;i<=n;i++){ sum=min(sum,bdfs(i,n)); } cout << sum; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...