# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
441675 | 2021-07-05T18:46:05 Z | Mahfel | Political Development (BOI17_politicaldevelopment) | C++17 | 7 ms | 844 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MXN = 5002; vector<int> adj[MXN]; int h[MXN]; bool k3,mark[MXN]; void DFS(int v , int dad) { mark[v] = 1; h[v] = (dad == -1 ? 0 : h[dad]+1); vector<int> be; for(auto u : adj[v]) { if(mark[u]) { if(h[u] == h[v]-2) k3 = 1; be.push_back(h[u]); continue; } DFS(u , v); } sort(be.begin() , be.end()); for(int i = 1 ; i < be.size() ; i++) { if(be[i]-be[i-1] == 1) { k3 = 1; break; } } } int main() { int n,m = 0,k; cin >> n >> k; for(int i = 0 ; i < n ; i++) { int d; cin >> d; m += d; for(int j = 0 ; j < d ; j++) { int u; cin >> u; adj[i].push_back(u); } } m /= 2; for(int i = 0 ; i < n ; i++) { if(mark[i]) continue; DFS(i , -1); } if(k3) { cout << "3\n"; return 0; } if(m > 0) { cout << "2\n"; } else { cout << "1\n"; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 424 KB | Output is correct |
3 | Correct | 5 ms | 588 KB | Output is correct |
4 | Correct | 5 ms | 716 KB | Output is correct |
5 | Correct | 5 ms | 588 KB | Output is correct |
6 | Correct | 5 ms | 588 KB | Output is correct |
7 | Correct | 5 ms | 588 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 412 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 424 KB | Output is correct |
3 | Correct | 5 ms | 588 KB | Output is correct |
4 | Correct | 5 ms | 716 KB | Output is correct |
5 | Correct | 5 ms | 588 KB | Output is correct |
6 | Correct | 5 ms | 588 KB | Output is correct |
7 | Correct | 5 ms | 588 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 412 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 6 ms | 588 KB | Output is correct |
12 | Correct | 5 ms | 588 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 5 ms | 620 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 5 ms | 588 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 5 ms | 588 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 3 ms | 588 KB | Output is correct |
21 | Correct | 3 ms | 588 KB | Output is correct |
22 | Correct | 1 ms | 332 KB | Output is correct |
23 | Correct | 6 ms | 844 KB | Output is correct |
24 | Correct | 2 ms | 332 KB | Output is correct |
25 | Correct | 7 ms | 844 KB | Output is correct |
26 | Incorrect | 6 ms | 840 KB | Output isn't correct |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 420 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Incorrect | 1 ms | 332 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 424 KB | Output is correct |
3 | Correct | 5 ms | 588 KB | Output is correct |
4 | Correct | 5 ms | 716 KB | Output is correct |
5 | Correct | 5 ms | 588 KB | Output is correct |
6 | Correct | 5 ms | 588 KB | Output is correct |
7 | Correct | 5 ms | 588 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 412 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 6 ms | 588 KB | Output is correct |
12 | Correct | 5 ms | 588 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 5 ms | 620 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 5 ms | 588 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 5 ms | 588 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 3 ms | 588 KB | Output is correct |
21 | Correct | 3 ms | 588 KB | Output is correct |
22 | Correct | 1 ms | 332 KB | Output is correct |
23 | Correct | 6 ms | 844 KB | Output is correct |
24 | Correct | 2 ms | 332 KB | Output is correct |
25 | Correct | 7 ms | 844 KB | Output is correct |
26 | Incorrect | 6 ms | 840 KB | Output isn't correct |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 424 KB | Output is correct |
3 | Correct | 5 ms | 588 KB | Output is correct |
4 | Correct | 5 ms | 716 KB | Output is correct |
5 | Correct | 5 ms | 588 KB | Output is correct |
6 | Correct | 5 ms | 588 KB | Output is correct |
7 | Correct | 5 ms | 588 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 412 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 6 ms | 588 KB | Output is correct |
12 | Correct | 5 ms | 588 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 5 ms | 620 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 5 ms | 588 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 5 ms | 588 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 3 ms | 588 KB | Output is correct |
21 | Correct | 3 ms | 588 KB | Output is correct |
22 | Correct | 1 ms | 332 KB | Output is correct |
23 | Correct | 6 ms | 844 KB | Output is correct |
24 | Correct | 2 ms | 332 KB | Output is correct |
25 | Correct | 7 ms | 844 KB | Output is correct |
26 | Incorrect | 6 ms | 840 KB | Output isn't correct |
27 | Halted | 0 ms | 0 KB | - |