Submission #1071378

#TimeUsernameProblemLanguageResultExecution timeMemory
1071378UmairAhmadMirzaBeech Tree (IOI23_beechtree)C++17
0 / 100
3 ms15128 KiB
#include <bits/stdc++.h> using namespace std; int const N=2e5+5; vector<int> child[N]; set<int> ch_col[N]; vector<int> ans; int dep[N]; void dfs(int node){ ans[node]=1; vector<int> ch; for(int i:child[node]){ dfs(i); dep[node]=max(dep[i]+1,dep[node]); if(dep[i]==1) ch.push_back(i); } if(ch.size()>1 || dep[node]>=2 || child[node].size()!=ch_col[node].size()){ ans[node]=0; return; } if(ch.size()==0) return; // if(ans[ch[0]]==0) // ans[node]=0; for(int c:ch_col[ch[0]]) if(ch_col[node].find(c)==ch_col[node].end()) ans[node]=0; return; } vector<int> beechtree(int n, int M, vector<int> P, vector<int> C){ for (int i = 1; i < n; ++i){ child[P[i]].push_back(i); ch_col[P[i]].insert(C[i]); } ans.resize(n); dfs(0); return ans; }
#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...
#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...