Submission #1306522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306522		Tymond	Capital City (JOI20_capital_city)	C++20	100 / 100	417 ms	39104 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int MAXN = 2e5 + 7;
const int INF = 1e9;
vi g[MAXN];
vi pos[MAXN];
int C[MAXN];
int blocked_color[MAXN];
int blocked[MAXN];
int parent[MAXN];
int used[MAXN];
int sz[MAXN];
int subtree[MAXN];
int usedCol[MAXN];
int idCol[MAXN];
int n, m;
int ans = INF;
vi comp;

void dfsInit(int v, int p){
    comp.pb(v);
    sz[v] = 1;
    for(auto u : g[v]){
        if(u == p || blocked[u]){
            continue;
        }
        dfsInit(u, v);
        sz[v] += sz[u];
    }
}

int findCentroid(int v, int p, int N){
    for(auto u : g[v]){
        if(blocked[u] || u == p){
            continue;
        }
        if(2 * sz[u] >= N){
            return findCentroid(u, v, N);
        }
    }
    return v;
}

void dfs2(int v, int p, int sub){
    subtree[v] = sub;
    parent[v] = p;
    used[v] = 0;
    idCol[C[v]] = -1;
    usedCol[C[v]] = 0;
    for(auto u : g[v]){
        if(u == p || blocked[u]){
            continue;
        }
        dfs2(u, v, sub);
    }
}

void centroid_decomposition(int v){
    comp.clear();
    dfsInit(v, v);

    int centroid = findCentroid(v, v, sz[v]);
    used[centroid] = 0;
    for(auto u : g[centroid]){
        if(blocked[u]){
            continue;
        }
        dfs2(u, centroid, u);
    }
    usedCol[C[centroid]] = 1;

    vi vec = {};
    bool flag = 1;
    int res = 0;
    if(blocked_color[C[centroid]]){
        flag = 0;
    }else{
        usedCol[C[centroid]] = 1;
        for(auto ele : pos[C[centroid]]){
            vec.pb(ele);
        }
    }

    while(sz(vec) && flag){
        int curr = vec.back();
        vec.pop_back();

        while(!used[curr]){
            used[curr] = 1;
            if(blocked_color[C[curr]]){
                flag = 0;
                break;
            }

            if(!usedCol[C[curr]]){
                usedCol[C[curr]] = 1;
                //cerr << "ADD: " << curr << ' ' << C[curr] << '\n';
                res++;
                for(auto ele : pos[C[curr]]){
                    if(!used[ele]){
                        vec.pb(ele);
                    }
                }
            }
            if(curr == centroid){
                break;
            }
            curr = parent[curr];
        }
    }

    // cerr << "======\n";
    // cerr << centroid << '\n';
    // debug(comp);
    // cerr << res << ' ' << flag << '\n';
    // for(auto ele : comp){
    //     cerr << ele << ' ' << used[ele] << '\n';
    // }
    if(flag){
        ans = min(ans, res);
    }

    blocked_color[C[centroid]] = 1;
    for(auto ele : comp){
        if(idCol[C[ele]] == -1){
            idCol[C[ele]] = subtree[ele];
        }

        if(idCol[C[ele]] != subtree[ele]){
            blocked_color[C[ele]] = 1;
        }
    }
    blocked[centroid] = 1;
    for(auto u : g[centroid]){
        if(!blocked[u]){
            centroid_decomposition(u);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    for(int i = 1; i <= n; i++){
        cin >> C[i];
        pos[C[i]].pb(i);
    }

    centroid_decomposition(1);
    cout << ans << '\n';

    return 0;
}

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