Submission #1242559

#TimeUsernameProblemLanguageResultExecution timeMemory
1242559uroskBeech Tree (IOI23_beechtree)C++20
9 / 100
2096 ms28732 KiB
#include "beechtree.h" #include "bits/stdc++.h" #define pb push_back #define popb pop_back #define fi first #define sc second #define si(a_) (ll)(a_.size()) #define all(a_) a_.begin(),a_.end() #define here cerr<<"========================================\n" #define dbg(X_) cerr<<#X_<<": "<<X_<<endl; #define ceri(a_,l_,r_) {for(ll i_=l_;i_<=r_;i_++) cerr<<a_[i_]<<" ";cerr<<endl;} using namespace std; using ll = int; using pll = pair<ll,ll>; const ll maxn = 200005; ll n,m; vector<pll> g[maxn]; bool oki[maxn]; vector<int> ans; ll up[maxn]; ll c[maxn]; ll cnt[maxn]; bool oksub(ll i){ bool oke = 1; for(pll p : g[i]){ ll j = p.fi,col = p.sc; if(cnt[col]) oke = 0; cnt[col] = 1; } for(pll p : g[i]){ ll j = p.fi,col = p.sc; cnt[col] = 0; } return oke; } ll dub[maxn]; ll rut; vector<ll> v; vector<ll> w; queue<ll> q; bool oke = 1; void dfs(ll u){ if(u!=rut) v.pb(u); for(pll p : g[u]) dfs(p.fi); } std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) { n = N,m = M; for(ll i = 2;i<=n;i++){ ll par = P[i-1]+1; g[par].pb({i,C[i-1]-1}); up[i] = par; c[i] = C[i-1]-1; } ans.resize(n); for(ll i = 0;i<n;i++) ans[i] = 0; for(ll i = 1;i<=n;i++){ rut = i; v.clear(); dfs(i); sort(all(v)); do{ w.clear(); w.pb(i); for(ll x : v) w.pb(x); bool oke = 1; for(ll i = 1;i<si(w);i++){ ll u = w[i]; if(w[cnt[c[u]]]!=up[u]) oke = 0; cnt[c[u]]++; } for(ll i = 1;i<si(w);i++) cnt[c[w[i]]]--; if(oke) ans[i-1] = 1; }while(next_permutation(all(v))); } 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...