Submission #1225417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225417		minhpk	Unique Cities (JOI19_ho_t5)	C++20	0 / 100	2097 ms	31420 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

using namespace std;
int a,b;
vector <int> z[1000005];
int low[1000005];
int high[1000005];
int col[1000005];

void dfs(int i,int par){
    low[i]=1;
    for (auto p:z[i]){
         if (p==par){
             continue;
         }
         high[p]=high[i]+1;
         dfs(p,i);
         low[i]=max(low[i],low[p]+1);
    }
}

stack<int> st;
int res[1000005];
bool cmp(int a,int b){
    return low[a]>low[b];
}
int u=0,v=0;
int cur;
void dfs1(int i,int par){
    if (i!=cur && z[i].size()==1){
        int k=st.size();
        res[i]=max(res[i],k);
        return;
    }
    sort(z[i].begin(),z[i].end(),cmp);
    int sta=0;
    if (par!=0){
        sta=1;
    }

    while (z[i].size()>2 && st.size() && high[i]-high[st.top()]<=low[z[i][2]]){
        st.pop();
    }
    st.push(i);
    dfs1(z[i][sta],i);
    while (st.size() && high[i]-high[st.top()]<=low[z[i][sta]]){
        st.pop();
    }
    int k=st.size();
    res[i]=max(res[i],k);

    for (auto p:z[i]){
         if (p==par){
             continue;
         }
         while (st.size() && high[st.top()]>=high[i]){
               st.pop();
         }
         st.push(i);
         dfs1(p,i);
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    for (int i=1;i<=a;i++){
         cin >> col[i];
    }
    dfs(1,0);
    int pre=0;
    for (int i=1;i<=a;i++){
         if (high[i]>pre){
             pre=high[i];
             u=i;
         }
    }
    dfs(u,0);
    pre=0;
    for (int i=1;i<=a;i++){
         if (high[i]>pre){
             pre=high[i];
             v=i;
         }
    }
  //  cout << u << " " << v << "\n";
    cur=u;
    dfs(u,0);
    dfs1(u,0);
    while (st.size()){
         st.pop();
    }
    cur=v;
    dfs(v,0);
    dfs1(v,0);

    for (int i=1;i<=a;i++){
         if (b==1){
             if (res[i]){
                 cout << 1 << "\n";
             }else{
                 cout << 0 << "\n";
             }
             continue;
         }
         cout << res[i] << "\n";
    }
    return 0;
}

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