Submission #875575

#	Time	Username	Problem	Language	Result	Execution time	Memory
875575		Darren0724	Capital City (JOI20_capital_city)	C++17	100 / 100	627 ms	45556 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int N=200005;
int n,m;
int ans=INF;
vector<int> c(N),sz(N),adj[N],can(N),no(N),pa(N),vis(N),c1[N],inq(N),noc(N),cnt1(N),use(N),tmp;
void dfs(int k){
    sz[k]=1;
    for(int j:adj[k]){
        if(j==pa[k]||no[j])continue;
        pa[j]=k;
        dfs(j);
        sz[k]+=sz[j];
    }
}
int get_cen(int k,int goal){
    for(int j:adj[k]){
        if(j==pa[k]||no[j])continue;
        if(sz[j]>goal){
            return get_cen(j,goal);
        }
    }
    return k;
}
void dfs2(int k){
    tmp.push_back(c[k]);
    //cout<<"dfs2:"<<k<<' '<<c[k]<<endl;
    for(int j:adj[k]){
        if(j==pa[k]||no[j])continue;
        dfs2(j);
    }
}
void solve(int p){
    pa[p]=p;
    dfs(p);
    int cen=get_cen(p,sz[p]/2);
    pa[cen]=cen;
    dfs(cen);
    //cout<<"cen:"<<cen<<' '<<c[cen]<<' '<<noc[c[cen]]<<endl;
    queue<int> q;
    int flag=1,cnt=0;
    if(!noc[c[cen]]){
        vector<int> vis1,inq1;
        vis1.push_back(cen);
        vis[cen]=1;
        q.push(c[cen]);
        inq[c[cen]]=1;
        inq1.push_back(c[cen]);
        noc[c[cen]]=1;
        while(q.size()){
            int p=q.front();
            q.pop();
            //cout<<"p:"<<p<<endl;
            cnt++;
            for(int j:c1[p]){
                int t=j;
                while(!vis[t]){
                    //cout<<"t:"<<t<<' '<<c[t]<<' '<<pa[t]<<endl;
                    if(!noc[c[t]]&&inq[c[t]]==0){
                        inq[c[t]]=1;
                        inq1.push_back(c[t]);
                        q.push(c[t]);
                    }
                    else if(inq[c[t]]==0){
                        flag=0;
                    }
                    vis[t]=1;
                    vis1.push_back(t);
                    t=pa[t];
                }
            }
        }
        for(int j:vis1){
            vis[j]=0;
        }
        for(int j:inq1){
            inq[j]=0;
        }
        //cout<<"flag:"<<flag<<' '<<cnt<<endl;
        if(flag){
            ans=min(ans,cnt);
        }
    }
    noc[c[cen]]=1;
    no[cen]=1;
    vector<int> tmp1;
    for(int j:adj[cen]){
        if(!no[j]){
            tmp.clear();
            dfs2(j);
            for(int j:tmp){
                if(!use[j]){
                    use[j]++;
                    cnt1[j]++;
                    tmp1.push_back(j);
                }
            }
            for(int j:tmp){
                if(use[j]){
                    use[j]--;
                }
            }
        }
    }
    for(int j:tmp1){
        //cout<<j<<' '<<cnt1[j]<<endl;
        if(cnt1[j]>=2){
            //cout<<"get out "<<j<<endl;
            noc[j]=1;
        }
        cnt1[j]=0;
    }
    for(int j:adj[cen]){
        if(!no[j]){
            solve(j);
        }
    }
}
int32_t main() {
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];
        c1[c[i]].push_back(i);
    }
    solve(1);
    cout<<ans-1<<endl;
 
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59