제출 #1223881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223881		minhpk	수도 (JOI20_capital_city)	C++20	100 / 100	643 ms	77484 KiB

capital_city

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,k;
vector <int> z[1000005];
int t[1000005];
int child[1000005];
int del[1000005];
int sz;
int mark[1000005];
int cur;
vector <int> col[1000005];
int up[1000005];
int min1=1e9;
bool vis[1000005];
bool viscol[1000005];
void predfs(int i,int par){
    child[i]=1;
    for (auto p:z[i]){
         if (p==par || del[p]){
             continue;
         }
         predfs(p,i);
         child[i]+=child[p];
    }
}
int centroid(int i,int par){
    for (auto p:z[i]){
         if (p==par || del[p]){
             continue;
         }
         if (child[p]>sz/2){
             return centroid(p,i);
         }
    }
    return i;
}
void dfs1(int i,int par){
    mark[i]=cur;
    up[i]=par;
    vis[i]=true;
    viscol[t[i]]=true;
    for (auto p:z[i]){
         if (p==par|| del[p]){
             continue;
         }
         dfs1(p,i);
    }
}

void decompose(int i){
     predfs(i,0);
     sz=child[i];
     int u=centroid(i,0);
     cur++;
     dfs1(u,0);
     vis[u]=false;
     viscol[t[u]]=false;
     bool check=true;

     queue<int> q;
     q.push(t[u]);
     int res=0;
     while (q.size()){
          int pos=q.front();
          res++;
          q.pop();
          for (auto p:col[pos]){
//               cout << p << "\n";
               if (mark[p]!=cur){
                  check=false;
                  break;
               }
               int t1=p;
               while (vis[t1]){
                     if (viscol[t[t1]]){
                         q.push(t[t1]);
                         viscol[t[t1]]=false;
                     }
                     vis[t1]=false;
                     t1=up[t1];
               }
          }
     }
     if (check){
         min1=min(min1,res-1);
     }
     del[u]=1;
//     cout << u << " " << check << " " << res << "\n";
     for (auto p:z[u]){
          if (del[p]){
             continue;
          }
          decompose(p);
     }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> k;
    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 >> t[i];
        col[t[i]].push_back(i);
    }
//    cout << "\n";
    decompose(1);
    cout << min1 << "\n";
    return 0;
}

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