Submission #848277

#TimeUsernameProblemLanguageResultExecution timeMemory
848277PlurmBeech Tree (IOI23_beechtree)C++17
0 / 100
124 ms44032 KiB
#include "beechtree.h" #include <bits/stdc++.h> using namespace std; vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) { vector<int> dep(N); dep[0] = 0; vector<set<int>> chs(N); vector<int> d1c; d1c.resize(M + 1, 0); vector<int> d2c; d2c.resize(M + 1, 0); vector<int> ret; ret.resize(N, 1); bool flag = true; vector<set<int>> ps(M + 1); for (int i = 1; i < N; i++) { if (P[i] == 0) dep[i] = 1; else dep[i] = 2; if (chs[P[i]].count(C[i])) { ret[P[i]] = 0; flag = false; } chs[P[i]].insert(C[i]); if (dep[i] == 2) { d2c[C[i]]++; ps[C[i]].insert(P[i]); } else { d1c[C[i]]++; } } if (!flag) ret[0] = 0; for (int i = 1; i <= M; i++) if (d2c[i] != 0 && d1c[i] == 0) ret[0] = 0; if (ret[0] == 0) return ret; // assume d1 is distinct set<int> active; set<int> activated; vector<int> dc; dc.resize(M + 1, 0); for (int i = 1; i < N; i++) { if (dep[i] == 2 && d2c[C[i]] == 1) { active.insert(P[i]); } else if (dep[i] == 1 && chs[i].empty()) { activated.insert(i); } if (dep[i] == 1) dc[C[i]]++; } int num = 0; while (!active.empty()) { int cur = *active.begin(); num++; activated.insert(cur); active.erase(cur); for (int x : chs[cur]) { d2c[x]--; dc[x]++; if (dc[x] <= num) { ret[0] = 0; return ret; } ps[x].erase(cur); if (d2c[x] == 1) { for (int y : ps[x]) active.insert(y); } } } for (int i = 0; i <= M; i++) if (dep[i] == 1 && activated.count(i) == 0) ret[0] = 0; return ret; }
#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...