# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
842435 | 2023-09-02T21:44:29 Z | arnold518 | Beech Tree (IOI23_beechtree) | C++17 | 2000 ms | 48976 KB |
#include "beechtree.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; int N, M; int P[MAXN+10], C[MAXN+10]; vector<int> adj[MAXN+10]; vector<pii> V[MAXN+10]; int ans[MAXN+10]; void dfs(int now) { for(int nxt : adj[now]) { V[C[nxt]].push_back({now, adj[nxt].size()==0}); dfs(nxt); } } vector<int> beechtree(int _N, int _M, vector<int> _P, vector<int> _C) { N=_N; M=_M; for(int i=1; i<=N; i++) P[i]=_P[i-1]+1, C[i]=_C[i-1]; for(int i=2; i<=N; i++) adj[P[i]].push_back(i); for(int i=1; i<=N; i++) { dfs(i); bool flag=true; sort(V+1, V+M+1, [&](const vector<pii> &p, const vector<pii> &q) { return p.size()<q.size(); }); for(int j=1; j<=M; j++) { sort(V[j].begin(), V[j].end()); for(int k=0; k+1<V[j].size(); k++) if(V[j][k].first==V[j][k+1].first) flag=false; } if(flag) { for(int j=2; j<=M; j++) { bool f1=0, f2=0; int p=0, q=0; for(; p<V[j].size(); p++) { if(q<V[j-1].size() && V[j-1][q].first==V[j][p].first) { if(V[j][p].second) f1=1; q++; } else { if(!V[j][p].second) f2=1; } } if(q!=V[j-1].size()) flag=false; if(f1 && f2) flag=false; } } ans[i]=flag; for(int j=1; j<=M; j++) V[j].clear(); } return vector<int>(ans+1, ans+N+1); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
4 | Correct | 3 ms | 10584 KB | Output is correct |
5 | Correct | 2 ms | 10584 KB | Output is correct |
6 | Correct | 2 ms | 10584 KB | Output is correct |
7 | Correct | 2 ms | 10584 KB | Output is correct |
8 | Correct | 2 ms | 10584 KB | Output is correct |
9 | Correct | 2 ms | 10588 KB | Output is correct |
10 | Correct | 2 ms | 10584 KB | Output is correct |
11 | Correct | 3 ms | 10584 KB | Output is correct |
12 | Correct | 2 ms | 10584 KB | Output is correct |
13 | Correct | 2 ms | 10584 KB | Output is correct |
14 | Correct | 2 ms | 10584 KB | Output is correct |
15 | Correct | 3 ms | 10588 KB | Output is correct |
16 | Correct | 2 ms | 10584 KB | Output is correct |
17 | Correct | 2 ms | 10704 KB | Output is correct |
18 | Incorrect | 2 ms | 10588 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
19 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
4 | Correct | 3 ms | 10584 KB | Output is correct |
5 | Correct | 2 ms | 10584 KB | Output is correct |
6 | Correct | 2 ms | 10584 KB | Output is correct |
7 | Execution timed out | 2047 ms | 48976 KB | Time limit exceeded |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 10704 KB | Output is correct |
2 | Correct | 3 ms | 10588 KB | Output is correct |
3 | Correct | 3 ms | 10588 KB | Output is correct |
4 | Correct | 4 ms | 10588 KB | Output is correct |
5 | Correct | 3 ms | 10588 KB | Output is correct |
6 | Correct | 3 ms | 10756 KB | Output is correct |
7 | Correct | 3 ms | 10588 KB | Output is correct |
8 | Correct | 3 ms | 10588 KB | Output is correct |
9 | Correct | 3 ms | 10704 KB | Output is correct |
10 | Correct | 3 ms | 10588 KB | Output is correct |
11 | Execution timed out | 2076 ms | 10768 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
4 | Correct | 2 ms | 10584 KB | Output is correct |
5 | Execution timed out | 2047 ms | 48976 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
4 | Correct | 2 ms | 10584 KB | Output is correct |
5 | Correct | 2 ms | 10584 KB | Output is correct |
6 | Correct | 2 ms | 10584 KB | Output is correct |
7 | Correct | 3 ms | 10584 KB | Output is correct |
8 | Correct | 2 ms | 10584 KB | Output is correct |
9 | Correct | 2 ms | 10584 KB | Output is correct |
10 | Correct | 2 ms | 10584 KB | Output is correct |
11 | Correct | 2 ms | 10584 KB | Output is correct |
12 | Correct | 2 ms | 10588 KB | Output is correct |
13 | Correct | 2 ms | 10584 KB | Output is correct |
14 | Correct | 3 ms | 10584 KB | Output is correct |
15 | Correct | 2 ms | 10584 KB | Output is correct |
16 | Correct | 2 ms | 10584 KB | Output is correct |
17 | Correct | 2 ms | 10584 KB | Output is correct |
18 | Correct | 3 ms | 10588 KB | Output is correct |
19 | Correct | 2 ms | 10584 KB | Output is correct |
20 | Correct | 2 ms | 10704 KB | Output is correct |
21 | Incorrect | 2 ms | 10588 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
4 | Correct | 2 ms | 10584 KB | Output is correct |
5 | Correct | 2 ms | 10588 KB | Output is correct |
6 | Correct | 2 ms | 10584 KB | Output is correct |
7 | Correct | 3 ms | 10584 KB | Output is correct |
8 | Correct | 2 ms | 10584 KB | Output is correct |
9 | Correct | 2 ms | 10584 KB | Output is correct |
10 | Correct | 2 ms | 10584 KB | Output is correct |
11 | Correct | 3 ms | 10588 KB | Output is correct |
12 | Correct | 2 ms | 10584 KB | Output is correct |
13 | Correct | 2 ms | 10704 KB | Output is correct |
14 | Incorrect | 2 ms | 10588 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
4 | Correct | 2 ms | 10584 KB | Output is correct |
5 | Correct | 2 ms | 10584 KB | Output is correct |
6 | Correct | 2 ms | 10584 KB | Output is correct |
7 | Correct | 3 ms | 10584 KB | Output is correct |
8 | Correct | 2 ms | 10584 KB | Output is correct |
9 | Correct | 2 ms | 10584 KB | Output is correct |
10 | Correct | 2 ms | 10584 KB | Output is correct |
11 | Correct | 2 ms | 10584 KB | Output is correct |
12 | Correct | 2 ms | 10588 KB | Output is correct |
13 | Correct | 2 ms | 10584 KB | Output is correct |
14 | Correct | 3 ms | 10584 KB | Output is correct |
15 | Correct | 2 ms | 10584 KB | Output is correct |
16 | Correct | 2 ms | 10584 KB | Output is correct |
17 | Correct | 2 ms | 10584 KB | Output is correct |
18 | Correct | 3 ms | 10588 KB | Output is correct |
19 | Correct | 2 ms | 10584 KB | Output is correct |
20 | Correct | 2 ms | 10704 KB | Output is correct |
21 | Incorrect | 2 ms | 10588 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
4 | Correct | 2 ms | 10584 KB | Output is correct |
5 | Correct | 2 ms | 10588 KB | Output is correct |
6 | Correct | 2 ms | 10584 KB | Output is correct |
7 | Correct | 3 ms | 10584 KB | Output is correct |
8 | Correct | 2 ms | 10584 KB | Output is correct |
9 | Correct | 2 ms | 10584 KB | Output is correct |
10 | Correct | 2 ms | 10584 KB | Output is correct |
11 | Correct | 3 ms | 10588 KB | Output is correct |
12 | Correct | 2 ms | 10584 KB | Output is correct |
13 | Correct | 2 ms | 10704 KB | Output is correct |
14 | Incorrect | 2 ms | 10588 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 10584 KB | Output is correct |
2 | Correct | 2 ms | 10584 KB | Output is correct |
3 | Correct | 2 ms | 10584 KB | Output is correct |
4 | Correct | 2 ms | 10584 KB | Output is correct |
5 | Correct | 2 ms | 10584 KB | Output is correct |
6 | Correct | 2 ms | 10584 KB | Output is correct |
7 | Correct | 3 ms | 10584 KB | Output is correct |
8 | Correct | 2 ms | 10584 KB | Output is correct |
9 | Correct | 2 ms | 10584 KB | Output is correct |
10 | Correct | 2 ms | 10584 KB | Output is correct |
11 | Correct | 2 ms | 10584 KB | Output is correct |
12 | Correct | 2 ms | 10588 KB | Output is correct |
13 | Correct | 2 ms | 10584 KB | Output is correct |
14 | Correct | 3 ms | 10584 KB | Output is correct |
15 | Correct | 2 ms | 10584 KB | Output is correct |
16 | Correct | 2 ms | 10584 KB | Output is correct |
17 | Correct | 2 ms | 10584 KB | Output is correct |
18 | Correct | 3 ms | 10588 KB | Output is correct |
19 | Correct | 2 ms | 10584 KB | Output is correct |
20 | Correct | 2 ms | 10704 KB | Output is correct |
21 | Incorrect | 2 ms | 10588 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
22 | Halted | 0 ms | 0 KB | - |