Submission #1078561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078561		vjudge1	Unique Cities (JOI19_ho_t5)	C++17	100 / 100	182 ms	42860 KiB

joi2019_ho_t5

    #include<bits/stdc++.h>
    #define ll long long
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define plx pair<ll,int>
    #define f first
    #define s second
    #define pb push_back
    #define all(x) x.begin(),x.end()
    #define vi vector<int>
    #define vl vector<ll>
    #define vvi vector<vi>
    using namespace std;
    const int mxn=2e5+5,inf=998244353;
    vector<int>g[mxn];
    int c[mxn];
    int ans[mxn]{0};
    stack<int>st;
    int cc[mxn]{0},cur=0;
    int d[mxn]{0},D[mxn]{0};
    void add(int x){
        if(++cc[c[D[x]]]==1)cur++;
        st.push(x);
    }
    void del(int x){
        while(!st.empty()&&st.top()>=x){
            if(--cc[c[D[st.top()]]]==0)cur--;
            st.pop();
        }
    }
    pii mx[mxn][2];
    int tmp=0,mem=0;
    void precal(int u,int p){
        if(mem<d[u])mem=d[u],tmp=u;
        mx[u][0]=mx[u][1]={0,0};
        for(auto v:g[u]){
            if(v==p)continue;
            d[v]=d[u]+1;precal(v,u);
            pii mxe = {mx[v][0].f+1,v};
            if(mxe>mx[u][0])swap(mxe,mx[u][0]);
            if(mxe>mx[u][1])swap(mxe,mx[u][1]);
        }
    }
    void cal(int u,int p,int de){
        D[de]=u;
        if(mx[u][0].s){
            if(mx[u][1].s)del(de-mx[u][1].f);
            add(de);
            cal(mx[u][0].s,u,de+1);
            del(de-mx[u][0].f);
        }if(!st.empty()&&st.top()==de)del(de);
        ans[u]=max(ans[u],cur);
        for(auto v:g[u]){
            if(v==p||v==mx[u][0].s)continue;
            if(st.empty()||st.top()!=de)add(de);
            cal(v,u,de+1);
        }
        if(!st.empty()&&st.top()==de)del(de);
    }
    int main(){
        ios_base::sync_with_stdio(0);cin.tie(0);
        int n,m;cin>>n>>m;
        for(int i=1;i<=n-1;i++){
            int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);
        }for(int i=1;i<=n;i++)cin>>c[i];
        precal(1,1);int rt1=tmp;memset(d,0,sizeof d);mem=0;tmp=0;
        precal(rt1,rt1);int rt2=tmp;
        cal(rt1,rt1,0);memset(cc,0,sizeof cc);memset(D,0,sizeof D);
        while(!st.empty())st.pop();memset(d,0,sizeof d);
        precal(rt2,rt2);cal(rt2,rt2,0);
        for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
    }

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:69:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   69 |         while(!st.empty())st.pop();memset(d,0,sizeof d);
      |         ^~~~~
joi2019_ho_t5.cpp:69:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   69 |         while(!st.empty())st.pop();memset(d,0,sizeof d);
      |                                    ^~~~~~

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