| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 941261 | 2024-03-08T12:01:06 Z | WanWan | Beech Tree (IOI23_beechtree) | C++17 | 81 ms | 27228 KB |
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 200005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int par[MAXN];
vector<int>childs[MAXN];
int st[MAXN],en[MAXN];
int TIME;
bool isleaf[MAXN];
bool child(int par, int child){
if(st[par]<=st[child] && en[par]>=en[child])return 1;
return 0;
}
void dfs(int x, int p){
st[x]=TIME++;
par[x]=p;
isleaf[x]=1;
for(auto v:childs[x]){
isleaf[x]=0;
dfs(v,x);
}
en[x]=TIME-1;
}
std::vector<int> beechtree(int n, int M, std::vector<int> P, std::vector<int> C)
{
vector<int> res=vector<int>(n,0);
for(int i=1;i<n;i++){
childs[P[i]].push_back(i);
}
dfs(0,-1);
for(int i=0;i<n;i++){ // check for this guy
if(isleaf[i]){
res[i]=1;
continue;
}
int nonleafs=0;
for(auto x:childs[i]){
if(!isleaf[x])nonleafs++;
}
if(nonleafs>1){
res[i]=0;
continue;
}
int leaf=-1;
for(auto x:childs[i]){
if(!isleaf[x])leaf=x;
}
if(leaf == -1){
// everyone is a leaf. just check that they are all different
unordered_set<int>os;
for(auto x:childs[i]){
os.insert(C[x]);
}
if(os.size() == childs[i].size()){
res[i]=1;
} else{
res[i]=0;
}
} else{
// 1 leaf.
bool bad=0;
unordered_set<int>ms;
for(auto x:childs[i]){
int sz=ms.size();
ms.insert(C[x]);
if(ms.size() == sz)bad=1;
}
for(auto x:childs[leaf]){
if(!isleaf[x])bad=1;
if(ms.find(C[x]) == ms.end()){
bad=1;
}
}
if(!bad){
res[i]=1;
}else{
res[i]=0;
}
}
}
return res;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Correct | 1 ms | 6492 KB | Output is correct |
| 3 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Correct | 1 ms | 6492 KB | Output is correct |
| 3 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Correct | 1 ms | 6488 KB | Output is correct |
| 3 | Correct | 2 ms | 6488 KB | Output is correct |
| 4 | Correct | 2 ms | 6492 KB | Output is correct |
| 5 | Correct | 1 ms | 6492 KB | Output is correct |
| 6 | Correct | 2 ms | 6492 KB | Output is correct |
| 7 | Correct | 1 ms | 6492 KB | Output is correct |
| 8 | Correct | 2 ms | 6488 KB | Output is correct |
| 9 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 10 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Correct | 1 ms | 6492 KB | Output is correct |
| 3 | Correct | 2 ms | 6492 KB | Output is correct |
| 4 | Correct | 2 ms | 6492 KB | Output is correct |
| 5 | Correct | 74 ms | 27228 KB | Output is correct |
| 6 | Correct | 81 ms | 27228 KB | Output is correct |
| 7 | Correct | 1 ms | 6488 KB | Output is correct |
| 8 | Correct | 1 ms | 6488 KB | Output is correct |
| 9 | Correct | 2 ms | 6748 KB | Output is correct |
| 10 | Correct | 2 ms | 6748 KB | Output is correct |
| 11 | Correct | 60 ms | 16732 KB | Output is correct |
| 12 | Correct | 58 ms | 14612 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Correct | 1 ms | 6492 KB | Output is correct |
| 3 | Correct | 2 ms | 6492 KB | Output is correct |
| 4 | Correct | 2 ms | 6492 KB | Output is correct |
| 5 | Correct | 1 ms | 6488 KB | Output is correct |
| 6 | Correct | 2 ms | 6492 KB | Output is correct |
| 7 | Correct | 2 ms | 6492 KB | Output is correct |
| 8 | Correct | 1 ms | 6492 KB | Output is correct |
| 9 | Correct | 1 ms | 6492 KB | Output is correct |
| 10 | Correct | 2 ms | 6492 KB | Output is correct |
| 11 | Correct | 1 ms | 6492 KB | Output is correct |
| 12 | Correct | 1 ms | 6492 KB | Output is correct |
| 13 | Correct | 2 ms | 6488 KB | Output is correct |
| 14 | Correct | 1 ms | 6492 KB | Output is correct |
| 15 | Correct | 2 ms | 6536 KB | Output is correct |
| 16 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 17 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Correct | 1 ms | 6492 KB | Output is correct |
| 3 | Correct | 2 ms | 6492 KB | Output is correct |
| 4 | Correct | 2 ms | 6492 KB | Output is correct |
| 5 | Correct | 1 ms | 6488 KB | Output is correct |
| 6 | Correct | 2 ms | 6492 KB | Output is correct |
| 7 | Correct | 2 ms | 6492 KB | Output is correct |
| 8 | Correct | 1 ms | 6492 KB | Output is correct |
| 9 | Correct | 1 ms | 6492 KB | Output is correct |
| 10 | Correct | 2 ms | 6492 KB | Output is correct |
| 11 | Correct | 1 ms | 6492 KB | Output is correct |
| 12 | Correct | 1 ms | 6492 KB | Output is correct |
| 13 | Correct | 2 ms | 6488 KB | Output is correct |
| 14 | Correct | 1 ms | 6492 KB | Output is correct |
| 15 | Correct | 2 ms | 6536 KB | Output is correct |
| 16 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 17 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Incorrect | 1 ms | 6492 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |