Submission #1180834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180834		user736482	Unique Cities (JOI19_ho_t5)	C++20	64 / 100	745 ms	69048 KiB

joi2019_ho_t5

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099

ll n,q,s,t,a,b,c,ans,k,e,m,pier,h,w,u;
ll sgtree[POT];
ll ile[200007];
ll co[200007],wyn1[200007],wyn2[200007],dpt1[200007],dpt2[200007],roz1[200007],roz2[200007];
vector<ll>g[200007],d[200007],d2[200007];

void ff(ll x){
    x++;
    x=co[x];
    ile[x]++;
    if(ile[x]==1)ans++;
}
void fff(ll x){
    x++;
    x=co[x];
    ile[x]--;
    if(ile[x]==0)ans--;
}

void add(ll pocz,ll kon,ll l, ll r,ll v,ll val){
    if(pocz>r || kon<l)return;
    if(pocz<=l && kon>=r)sgtree[v]+=val;
    else{
        add(pocz,kon,l,(l+r)/2,v*2,val);
        add(pocz,kon,(l+r)/2+1,r,v*2+1,val);
    }
}

ll sm(ll v){
    if(v==0)return 0;
    return sgtree[v]+sm(v/2);
}

pair<ll,ll>dfs(ll v,ll pop){
    pair<ll,ll>bst={-1,v};
    for(ll i : g[v]){
        if(i==pop)continue;
        
        bst=max(bst,dfs(i,v));
    }
    bst.ff++;
    return  bst;
}
void dfs2(ll v,ll pop,ll dpth){
    dpt1[v]=dpth;
    for(ll i : g[v]){
        if(i==pop)continue;
        dfs2(i,v,dpth+1);
        roz1[v]=max(roz1[v],1+roz1[i]);
        d[v].pb(i);
    }
    //cout<<v<<" "<<dpt1[v]<<" "<<roz1[v]<<"\n";
    
}
void dfs3(ll v,ll pop,ll dpth){
    dpt2[v]=dpth;
    for(ll i : g[v]){
        if(i==pop)continue;
        dfs3(i,v,dpth+1);
        roz2[v]=max(roz2[v],1+roz2[i]);
        d2[v].pb(i);
    }
    
}
void dfs4(ll v){
   // cout<<v<<"    ";
    add(1+max(0LL,dpt1[v]-roz1[v]-2),dpt1[v]-1,1,POT/2,1,-1);
   // cout<<1+max(0LL,dpt1[v]-roz1[v]-2)<<" "<<dpt1[v]-1<<"\n";
   // cout<<"xd"<<flush;
    for(ll i : d[v]){
        add(1+max(0LL,dpt1[v]-roz1[i]-1),dpt1[v],1,POT/2,1,1);
    //    cout<<1+max(0LL,dpt1[v]-roz1[i]-1)<<" "<<dpt1[v]<<"\n";
    }
 //   cout<<ans<<" "<<sm(2+POT/2-1)<<" "<<dpt1[v]<<" "<<roz1[v]<<" "<<flush;
    if(dpt1[v]-roz1[v]>0)
    if(sm(dpt1[v]-roz1[v]+POT/2-1)==0){ff(dpt1[v]-roz1[v]-1);//cout<<dpt1[v]-roz1[v]<<" ";
        
    }
    if(dpt1[v]-roz1[v]>1)
    if(sm(dpt1[v]-roz1[v]-1+POT/2-1)==0){ff(dpt1[v]-roz1[v]-1-1);//cout<<dpt1[v]-roz1[v]-1<<" ";
        
    }
    wyn1[v]=ans;
  //  cout<<ans<<"\n";
    for(ll i : d[v])
        dfs4(i);
   
    if(dpt1[v]-roz1[v]>0)
    if(sm(dpt1[v]-roz1[v]+POT/2-1)==0)fff(dpt1[v]-roz1[v]-1);
    if(dpt1[v]-roz1[v]>1)
    if(sm(dpt1[v]-roz1[v]-1+POT/2-1)==0)fff(dpt1[v]-roz1[v]-1-1);
     add(1+max(0LL,dpt1[v]-roz1[v]-2),dpt1[v]-1,1,POT/2,1,1);
    for(ll i : d[v]){
        add(1+max(0LL,dpt1[v]-roz1[i]-1),dpt1[v],1,POT/2,1,-1);
    }
}

void dfs5(ll v){
    
    add(1+max(0LL,dpt2[v]-roz2[v]-2),dpt2[v]-1,1,POT/2,1,-1);
    
    for(ll i : d2[v]){
        add(1+max(0LL,dpt2[v]-roz2[i]-1),dpt2[v],1,POT/2,1,1);
    }
    if(dpt2[v]-roz2[v]>0)
    if(sm(dpt2[v]-roz2[v]+POT/2-1)==0)ff(dpt2[v]-roz2[v]-1);
    if(dpt2[v]-roz2[v]>1)
    if(sm(dpt2[v]-roz2[v]-1+POT/2-1)==0)ff(dpt2[v]-roz2[v]-1-1);
    wyn2[v]=ans;
    for(ll i : d2[v])
        dfs5(i);
    if(dpt2[v]-roz2[v]>0)
    if(sm(dpt2[v]-roz2[v]+POT/2-1)==0)fff(dpt2[v]-roz2[v]-1);
    if(dpt2[v]-roz2[v]>1)
    if(sm(dpt2[v]-roz2[v]-1+POT/2-1)==0)fff(dpt2[v]-roz2[v]-1-1);
    add(1+max(0LL,dpt2[v]-roz2[v]-2),dpt2[v]-1,1,POT/2,1,1);
    
    for(ll i : d2[v]){
        add(1+max(0LL,dpt2[v]-roz2[i]-1),dpt2[v],1,POT/2,1,-1);
    }
}

int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(ll i=1;i<n;i++){
        cin>>a>>b;
        a--;
        b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    for(ll i=0;i<n;i++){
        cin>>co[i];
    }
    w=dfs(0,-1).ss;
    u=dfs(w,-1).ss;
  //  cout<<u<<" "<<w<<"      ";
    dfs2(u,-1,0);//cout<<"\n\n";
    dfs3(w,-1,0);
    dfs4(u);//cout<<"\n\n";
    dfs5(w);
    for(ll i=0;i<n;i++){
        if(dpt1[i]>dpt2[i])
            cout<<wyn1[i]<<"\n";
        else
            cout<<wyn2[i]<<"\n";
    }
}

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