Submission #474016

#TimeUsernameProblemLanguageResultExecution timeMemory
474016julian33Cat in a tree (BOI17_catinatree)C++14
51 / 100
1084 ms29316 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=2e5+5,mxL=19; //make sure this is right const int mod=1e9+7; vector<int> graph[mxN],path; int bad[mxN],ht[mxN],seen[mxN]; priority_queue<pii> q; int up[mxN][mxL]; void dfs(int at,int p=-1){ up[at][0]=~p?p:at; for(int i=1;i<mxL;i++) up[at][i]=up[up[at][i-1]][i-1]; for(int &i:graph[at]){ if(i==p) continue; ht[i]=ht[at]+1; dfs(i,at); } q.push({ht[at],at}); } int jump(int a,int k){ for(int i=0;i<mxL;i++){ if(k&(1<<i)) a=up[a][i]; } return a; } int lca(int a,int b){ if(ht[a]>ht[b]) swap(a,b); b=jump(b,ht[b]-ht[a]); if(a==b) return a; for(int i=mxL-1;i>=0;i--){ if(up[a][i]!=up[b][i]){ a=up[a][i]; b=up[b][i]; } } return up[a][0]; } void paint(int at,int d,int dep){ if(d==0 || ht[at]>dep || seen[at]) return; bad[at]=1; seen[at]=1; path.pb(at); for(int &i:graph[at]) paint(i,d-1,dep); } int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,d; cin>>n>>d; for(int i=1;i<n;i++){ int x; cin>>x; graph[x].pb(i); graph[i].pb(x); } dfs(0); int ans=0; vector<int> used; while(!q.empty()){ int at=q.top().second; q.pop(); if(d<=200){ if(bad[at]) continue; ans++; paint(at,d,ht[at]); while(sz(path)){ seen[path.back()]=0; path.pop_back(); } } else{ int no=0; for(int &i:used){ if(ht[at]+ht[i]-2*ht[lca(at,i)]<d){ no=1; break; } } if(no) continue; ans++; used.pb(at); } } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...