Submission #1226662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226662		MarwenElarbi	Unique Cities (JOI19_ho_t5)	C++20	32 / 100	513 ms	47748 KiB

joi2019_ho_t5

#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;
}

• Subtask 1: 0 / 4
• Subtask 2: 32 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32