제출 #676866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676866		alvingogo	수도 (JOI20_capital_city)	C++14	100 / 100	404 ms	39076 KiB

capital_city

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

vector<int> vis;
vector<vector<int> > vp;
struct no{
    vector<int> ch;
    int sz=1;
    int fa=-1;
    int t;
    int vz=0;
    int op=1;
    int up=0;
};
vector<no> v;
vector<int> gg;
int ans=1e9;
void dfs(int r,int f,int t){
    v[r].sz=1;
    v[r].fa=f;
    v[r].op=1;
    for(auto h:v[r].ch){
        if(h!=f && !v[h].vz){
            dfs(h,r,t);
            v[r].sz+=v[h].sz;
        }
    }
    if(t){
        gg.push_back(r);
    }
}
int fc(int r,int n){
    for(auto h:v[r].ch){
        if(h!=v[r].fa && !v[h].vz && v[h].sz>n/2){
            return fc(h,n);
        }
    }
    return r;
}
void dc(int r){
    dfs(r,r,1);
    int n=gg.size();
    int cd=fc(r,n);
    dfs(cd,cd,0);
    int mx=0;
    int flag=1;
    set<int> s;
    s.insert(v[cd].t);
    set<int> s2;
    while(s.size()){
        mx++;
        auto h=*s.begin();
        s.erase(h);
        s2.insert(h);
        for(auto y:vp[h]){
            if(!v[y].op){
                flag=0;
                break;
            }
            int p=y;
            while(!v[p].up){
                v[p].up=1;
                if(s2.find(v[p].t)==s2.end()){
                    s.insert(v[p].t);
                }
                
                p=v[p].fa;
            }
        }
        if(flag==0){
            break;
        }
    }
    if(flag){
        ans=min(ans,mx-1);
    }
    for(auto h:gg){
        v[h].op=0;
        v[h].up=0;
    }
    for(auto h:vp[v[cd].t]){
        v[h].vz=1;
    }
    vector<int> y;
    y.swap(gg);
    for(auto h:y){
        if(!v[h].vz){
            dc(h);
        }
    }
}
int main(){
    AquA;
    int n,k;
    cin >> n >> k;
    v.resize(n);
    vp.resize(k);
    for(int i=1;i<n;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        v[a].ch.push_back(b);
        v[b].ch.push_back(a);
    }
    for(int i=0;i<n;i++){
        cin >> v[i].t;
        v[i].t--;
        vp[v[i].t].push_back(i);
    }
    dc(0);
    cout << ans << "\n";
    return 0;
}

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