Submission #1039138

#TimeUsernameProblemLanguageResultExecution timeMemory
1039138n3rm1nPolitical Development (BOI17_politicaldevelopment)C++17
4 / 100
131 ms34392 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN = 5005; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int n, k; vector < int > g[MAXN]; int m; int ok = 0, a[MAXN][MAXN]; int used[MAXN]; void dfs(int beg, int p) { used[beg] = 1; for (auto nb: g[beg]) { if(used[nb] && a[p][nb] && a[nb][beg])ok = 1; if(used[nb])continue; dfs(nb, beg); } } void read() { cin >> n >> k; for (int i = 0; i < n; ++ i) { int cnt; cin >> cnt; m += cnt; while(cnt --) { int x; cin >> x; a[i][x] = 1; g[i].push_back(x); } } if(k == 1) { cout << 1 << endl; exit(0); } if(k == 2) { if(m)cout << 2 << endl; else cout << 1 << endl; exit(0); } if(k == 3) { int ans = 1; if(m)ans = 2; for (int i = 0; i < n; ++ i) { memset(used, 0, sizeof(used)); dfs(i, -1); } if(ok)ans = 3; cout << ans << endl; } } int main() { speed(); read(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...