Submission #570500

#TimeUsernameProblemLanguageResultExecution timeMemory
570500HuyBosses (BOI16_bosses)C++17
67 / 100
1583 ms980 KiB
#include<bits/stdc++.h> //#define int long long #define pii pair<int,int> #define fi first #define se second using namespace std; using ll = long long; using ldb = long double; const int N = (int)1e8; const int maxN = (int)3e5 + 1; const int mod = 1e9 + 7; void InputFile() { //freopen("scrivener.inp","r",stdin); //freopen("scrivener.out","w",stdout); //freopen("test.out","r",stdin); } void FastInput() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } int n; vector<vector<int>> adj1; vector<int> adj2[5005]; int res = mod; int check = 0; void Read() { cin >> n; adj1.resize(n+1); for(int i = 1;i <= n;i++) { int k; cin >> k; for(int j = 1;j <= k;j++) { int t; cin >> t; adj1[t].push_back(i); } } } int dp[maxN]; int trace[maxN]; int isvis[maxN]; int su[maxN]; void Trace(int v) { isvis[v] = 1; int u = trace[v]; if(u == 0) return; adj2[u].push_back(v); if(!isvis[u]) Trace(u); } void DFS(int u) { su[u] = 1; for(int v : adj2[u]) { DFS(v); su[u] += su[v]; } check += su[u]; } void BFS(int sta) { for(int i = 1;i <= n;i++) { dp[i] = mod; isvis[i] = 0; trace[i] = 0; adj2[i].clear(); } dp[sta] = 0; queue<int> q; q.push(sta); do { int u = q.front(); q.pop(); for(int v : adj1[u]) { if(dp[v] > dp[u] + 1) { dp[v] = dp[u] + 1; trace[v] = u; q.push(v); } } } while(!q.empty()); for(int i = 1;i <= n;i++) { if(dp[i] >= mod) return; if(!isvis[i]) Trace(i); } check = 0; DFS(sta); res = min(res,check); } void Solve() { for(int i = 1;i <= n;i++) BFS(i); cout << res; } void Debug() { //Main_sub(); //Naive(); } int32_t main() { FastInput(); //InputFile(); //int sub_type; //cin >> sub_type; //Sieve(); int test; //cin >> test; test = 1; while(test--) //for(int prc = 1; prc <= test; prc++) { Read(); Solve(); //Debug(); } } /* 4 1 1 1 1 1 1 2 2 3 3 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...