# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
871459 | 2023-11-10T21:55:19 Z | AdamGS | Beech Tree (IOI23_beechtree) | C++17 | 1 ms | 1116 KB |
#include "beechtree.h" #include<bits/stdc++.h> using namespace std; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e3+7; vector<pair<int,int>>V[LIM]; int T[LIM][LIM], czy[LIM], ile[LIM]; void DFS(int x) { czy[x]=ile[x]=1; for(int i=1; i<V[x].size(); ++i) if(V[x][i].st==V[x][i-1].st) czy[x]=0; for(auto i : V[x]) { DFS(i.nd); ile[x]+=ile[i.nd]; if(!czy[i.nd]) czy[x]=0; } } int wiekszy(int x, int y) { if(T[x][y]!=0) return T[x][y]; T[x][y]=1; int l=0; for(auto i : V[y]) { while(l<V[x].size() && V[x][l].st<i.st) ++l; if(l==V[x].size() || V[x][l].st>i.st) { T[x][y]=-1; break; } if(wiekszy(V[x][l].nd, i.nd)==-1) { T[x][y]=-1; break; } ++l; } return T[x][y]; } vector<int>beechtree(int n, int m, vector<int>P, vector<int>C) { rep(i, n-1) V[P[i+1]].pb({C[i+1], i+1}); rep(i, n) sort(all(V[i])); DFS(0); for(int i=n-1; i>=0; --i) for(int j=n-1; j>i; --j) { wiekszy(i, j); wiekszy(j, i); } vector<int>ans(n); rep(i, n) ans[i]=czy[i]; for(int i=n-1; i>=0; --i) { vector<pair<int,int>>S; for(auto j : V[i]) { if(!ans[j.nd]) ans[i]=0; S.pb({ile[j.nd], j.nd}); } sort(all(S)); rep(a, S.size()) rep(b, a) if(T[S[a].nd][S[b].nd]==-1) ans[i]=0; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1004 KB | Output is correct |
2 | Correct | 1 ms | 1116 KB | Output is correct |
3 | Correct | 1 ms | 860 KB | Output is correct |
4 | Correct | 1 ms | 1116 KB | Output is correct |
5 | Incorrect | 1 ms | 1116 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Incorrect | 0 ms | 348 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Incorrect | 0 ms | 348 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Incorrect | 0 ms | 348 KB | 2nd lines differ - on the 1st token, expected: '0', found: '1' |
6 | Halted | 0 ms | 0 KB | - |