제출 #1057530

#제출 시각아이디문제언어결과실행 시간메모리
1057530n1k참나무 (IOI23_beechtree)C++17
80 / 100
2064 ms258840 KiB
#include "beechtree.h" #include <bits/stdc++.h> using namespace std; std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C){ vector<multiset<pair<int, map<int, int>>>> c(N); vector<vector<int>> g(N); vector<int> ans(N, 1), sz(N, 1), len(N); for(int i=1; i<N; i++){ g[P[i]].push_back(i); } auto check = [&](auto a, auto b){ bool ok = a.size() >= b.size(); for(auto [k, v]:b){ ok &= a[k]>=v; } return ok; }; auto add = [&](auto p, auto u){ len[u]+=p.second.size(); bool ok = 1; auto it = c[u].insert(p); if(next(it)!=c[u].end()){ ok&=check(next(it)->second, it->second); } if(it!=c[u].begin()){ ok&=check(it->second, prev(it)->second); } return ok; }; function<void(int)> dfs = [&](int u){ map<int, int> cur; for(auto v:g[u]){ dfs(v); sz[u]+=sz[v]; ans[u]&=ans[v]; ans[u]&= !cur.count(C[v]); cur[C[v]] = sz[v]; if(len[u] < len[v]){ swap(c[u], c[v]); swap(len[u], len[v]); } // insert for(auto p:c[v]){ ans[u]&=add(p, u); } } ans[u]&=add(make_pair(sz[u], cur), u); }; 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...