Submission #1226197

#TimeUsernameProblemLanguageResultExecution timeMemory
1226197MarwenElarbiUnique Cities (JOI19_ho_t5)C++20
0 / 100
299 ms12320 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]>mn) ans[x]|=1;  
    //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()){
            if(depth[x]-tab[tab.size()-2]+1<mn) dfs(u,x,depth[x]);
            else dfs(u,x,mn);
        }else{
            if(depth[x]-tab.back()+1<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);
    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...