Submission #1227092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227092		MarwenElarbi	Unique Cities (JOI19_ho_t5)	C++20	0 / 100	367 ms	16268 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int nax=2e5+7;
vector<int> adj[nax];
int dp[nax];
int depth[nax];
int ans[nax];
int dis=0;
int fir,sec;
int n,m;
// 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
pair<int,int> segtree[nax*4];
void build(int pos,int l,int r){
    if(l>r) return;
    if(l==r) {
        segtree[pos]={1,0};
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos].se=0;
    segtree[pos].fi=segtree[pos*2+1].fi+segtree[pos*2+2].fi;
}
void update(int pos,int l,int r,int left,int right,int value){
    if(l>r||l>right||r<left) return;
    //cout <<l<<" "<<r<<" "<<left<<" "<<right<<endl;
    if(l>=left&&r<=right){
        segtree[pos].se+=value;
        return;
    }
    int mid=(r+l)/2;
    update(pos*2+1,l,mid,left,right,value);
    update(pos*2+2,mid+1,r,left,right,value);
    segtree[pos].fi=(segtree[pos*2+1].se==0 ? segtree[pos*2+1].fi : 0 ) + (segtree[pos*2+2].se==0 ? segtree[pos*2+2].fi : 0 ) ;
}
int query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return 0;
    if(l>=left&&r<=right) {
        return (segtree[pos].se ? 0 : segtree[pos].fi) ;
    }
    int mid=(r+l)/2;
    return query(pos*2+1,l,mid,left,right)+query(pos*2+2,mid+1,r,left,right);
}
void dfs(int x,int p){
    vector<int> tab;
    tab.push_back(0);
    ans[x]=max(ans[x],query(0,0,n-1,0,depth[x]-dp[x]));  
    //bcout <<p<<" "<< x<<" "<<dp[x]<<" "<<depth[x]<<" "<<depth[x]-dp[x]<<" "<<query(0,0,n-1,0,depth[x]-dp[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;
            //cout <<max(0,depth[x]-tab.back())<<" "<<depth[x]-1<<" "<< segtree[0].fi<<endl;
            update(0,0,n-1,max(0,depth[x]-tab.back()),depth[x]-1,1);
            dfs(u,x);
            update(0,0,n-1,max(0,depth[x]-tab.back()),depth[x]-1,-1);
        }else{
            //cout <<u<<" "<<tab[tab.size()-2]<<" "<<max(0,depth[x]-tab[tab.size()-2])<<" "<<depth[x]-1<<" "<< segtree[7].fi<<endl;
            update(0,0,n-1,max(0,depth[x]-tab[tab.size()-2]),depth[x]-1,1);
            dfs(u,x);
            update(0,0,n-1,max(0,depth[x]-tab[tab.size()-2]),depth[x]-1,-1);
        }
    }
}
int main() {
    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;
    build(0,0,n-1);
    compute_depth(fir,-1);
    dfs(fir,-1);
    build(0,0,n-1);
    depth[sec]=0;
    compute_depth(sec,-1);
    dfs(sec,-1);
    for(int i=0;i<n;i++) {
      if(m==1){
        cout << (ans[i] ? 1 : 0 ) <<endl;
      }else{
        cout <<ans[i]<<endl;
      }
    }
}

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