Submission #999176

#	Time	Username	Problem	Language	Result	Execution time	Memory
999176		snpmrnhlol	Capital City (JOI20_capital_city)	C++17	100 / 100	353 ms	35412 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int inf = 2e9;
vector <int> e[N];
int v[N];
int sub[N];
vector <int> pos[N];
bool bad[N];
bool tree[N];
bool vis[N];
bool vis2[N];
int ans = inf;
int pr[N];
void cendecomp(int node){
    int sz = 0;
    int cen = -1,mn = inf;
    auto dfs = [&](auto self, int node, int p) -> void{
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
        }
        sz++;
    };
    auto dfs2 = [&](auto self, int node, int p) -> void{
        int mx = -1;
        sub[node] = 1;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
            sub[node]+=sub[i];
            mx = max(mx,sub[i]);
        }
        mx = max(mx,sz - sub[node]);
        if(mx < mn){
            mn = mx;
            cen = node;
        }
    };
    auto dfs3 = [&](auto self, int node, int p) -> void{
        vis[node] = 0;
        tree[node] = 0;
        vis2[v[node]] = 0;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
        }
    };
    auto dfs4 = [&](auto self, int node, int p) -> void{
        pr[node] = p;
        tree[node] = 1;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
        }
    };
    dfs(dfs, node, -1);
    dfs2(dfs2, node, -1);
    dfs4(dfs4, cen, -1);
    queue <int> q;
    q.push(cen);
    vis[cen] = 1;
    bool ok = 1;
    int nr = 0;
    while(!q.empty()){
        int x = q.front();
        //cout<<"investigate:"<<x<<'\n';
        q.pop();
        if(!vis2[v[x]]){
            vis2[v[x]] = 1;
            nr++;
            for(auto i:pos[v[x]]){
                if(!tree[i]){
                    ok = 0;
                    break;
                }
                if(tree[i] && !vis[i]){
                    vis[i] = 1;
                    q.push(i);
                }
            }
            if(!ok)break;
        }
        if(pr[x] != -1 && !vis[pr[x]]){
            vis[pr[x]] = 1;
            q.push(pr[x]);
        }
    }
    if(ok){
        ans = min(ans,nr);
    }
    dfs3(dfs3, cen, -1);
    //cout<<cen<<' '<<nr<<' '<<ok<<'\n';
    bad[cen] = 1;
    for(auto i:e[cen]){
        if(!bad[i]){
            cendecomp(i);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i = 0;i < n - 1;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        e[u].push_back(w);
        e[w].push_back(u);
    }
    for(int i = 0;i < n;i++){
        cin>>v[i];
        v[i]--;
        pos[v[i]].push_back(i);
    }
    cendecomp(0);
    cout<<ans - 1<<'\n';
    return 0;
}

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