Submission #1070071

#TimeUsernameProblemLanguageResultExecution timeMemory
1070071bleahbleahBeech Tree (IOI23_beechtree)C++17
58 / 100
2086 ms120312 KiB
#include "beechtree.h" #include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 3e5 + 5; vector<pii> g[nmax]; vector<int> P, C; unordered_set<int> colors[nmax], play[nmax]; bool isanc(unordered_set<int>& A, unordered_set<int>& B) { if(sz(A) < sz(B)) return 0; for(auto &x : B) if(!A.count(x)) return 0; return 1; } vector<int> sol; int h[nmax]; bool superimposable(int x, int y) { // x peste y //if(sz(g[x]) == 0 || x == y) return 1; //if(calc[x][y]) return SI[x][y]; map<int, int> gy; for(auto [a, c] : g[y]) gy[c] = a; //calc[x][y] = 1; //SI[x][y] = 1; for(auto [a, c] : g[x]) { if(gy.count(c) == 0) { return 0; } if(!superimposable(a, gy[c])) { return 0; } } return 1; } int area[nmax]; void insert(int& works, map<int, int>& st, int node) { if(!works) return; auto it = st.upper_bound(area[node]); if(it == st.end()); else if(!superimposable(node, it -> second)) { works = 0; return; } if(it == st.begin()); else if(!superimposable(prev(it) -> second, node)) { works = 0; return; } st[area[node]] = node; return; } map<int, int> dfs(int node) { map<int, int> here; sol[node] = 1; area[node] = 1; for(auto [x, c] : g[node]) { auto T = dfs(x); area[node] += area[x]; sol[node] &= sol[x]; if(sz(T) > sz(here)) swap(here, T); for(auto [a, x] : T) insert(sol[node], here, x); } insert(sol[node], here, node); if(sz(g[node]) != sz(colors[node])) sol[node] = 0; return here; } std::vector<int> beechtree(int N, int M, std::vector<int> P_, std::vector<int> C_) { P = P_; C = C_; for(int i = 1; i < N; i++) { g[P[i]].emplace_back(i, C[i]); colors[P[i]].emplace(C[i]); } sol.assign(N, 0); dfs(0); return sol; } /** Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen -- */
#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...