제출 #1226662

#제출 시각아이디문제언어결과실행 시간메모리
1226662MarwenElarbiUnique Cities (JOI19_ho_t5)C++20
32 / 100
513 ms47748 KiB
#include <bits/stdc++.h> using namespace std; const int nax=2e5+7; vector<int> adj[nax]; int dp[nax]; int depth[nax]; bool ans[nax]; int dis=0; int fir,sec; // compute diametre void precompute(int x,int cur,int p,int cnt){ if(dis<cur){ dis=cur; (cnt ? sec : fir)=x; } for(auto u:adj[x]){ if(u==p) continue; precompute(u,cur+1,x,cnt); } } // compute the height of every subtree void compute_depth(int x,int p){ dp[x]=1; for(auto u:adj[x]){ if(u==p) continue; depth[u]=depth[x]+1; compute_depth(u,x); dp[x]=max(dp[x],dp[u]+1); } } //nabnab void dfs(int x,int p,int mn){ vector<int> tab; tab.push_back(0); if(depth[x]-dp[x]+1>mn) ans[x]|=1; //cout <<p<<" "<< x<<" "<<dp[x]<<" "<<depth[x]<<" "<<mn<<" "<<depth[x]-dp[x]+1<<" "<<ans[x]<<endl; //dakhalt houni kol heights mt3 kol subtrees for(auto u:adj[x]){ if(u==p) continue; tab.push_back(dp[u]); } //sort sort(tab.begin(),tab.end()); for(auto u:adj[x]){ if(u==p) continue; if(dp[u]==tab.back()){ //cout << tab[tab.size()-2]<<endl; if(depth[x]-tab[tab.size()-2]<=mn) dfs(u,x,depth[x]); else dfs(u,x,mn); }else{ if(depth[x]-tab.back()<=mn) dfs(u,x,depth[x]); else dfs(u,x,mn); } } } int main() { int n,m; cin>>n>>m; for (int i = 0; i < n-1; ++i) { int x,y; cin>>x>>y; x--;y--; adj[x].push_back(y); adj[y].push_back(x); } precompute(0,0,-1,0); precompute(fir,0,-1,1); //cout <<fir<<" "<<sec<<endl; depth[fir]=0; compute_depth(fir,-1); dfs(fir,-1,0); depth[sec]=0; compute_depth(sec,-1); dfs(sec,-1,0); for(int i=0;i<n;i++) cout<<ans[i]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...