Submission #1242572

#TimeUsernameProblemLanguageResultExecution timeMemory
1242572banganBeech Tree (IOI23_beechtree)C++20
0 / 100
2099 ms70984 KiB
#include "beechtree.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define ALL(a) a.begin(), a.end() const int MXN = 200200; int n; int m; vector<int> p; vector<int> c; vector<int> adj[MXN]; bool leaf[MXN]; int ptr[MXN]; bool valid(vector<int> vec) { bool ans = true; for (auto it = next(vec.begin()); it != vec.end(); it++) { if (vec.size() <= ptr[c[*it]] || vec[ptr[c[*it]]] != p[*it]) ans = false; ptr[c[*it]]++; } for (int v : vec) ptr[c[v]] = 0; return ans; } int h[MXN]; int sz[MXN]; bool cmp(int v, int u) { if (h[v]==h[u]) return sz[v]>sz[u]; return h[v]<h[u]; } vector<int> ans; vector<int> dfs(int v) { if (leaf[v]) { ans[v] = 1; return {v}; } vector<int> norm{v}, esp; for (int u : adj[v]) { auto vec = dfs(u); for (int x : vec) (leaf[x] ? esp : norm).pb(x); } sort(ALL(norm), cmp); sort(ALL(esp), [&](int x, int y) { return cmp(p[x], p[y]); }); vector<int> res; for (int x : norm) res.pb(x); for (int x : esp) res.pb(x); ans[v] = valid(res); return res; } vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) { n = N; m = M; p = P; c = C; for (int i=1; i<n; i++) adj[p[i]].pb(i); for (int i=0; i<n; i++) leaf[i] = adj[i].empty(); 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...