Submission #1211057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211057		dosts	Capital City (JOI20_capital_city)	C++20	1 / 100	287 ms	74028 KiB

capital_city

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e9, inf = 2e9,MAXN = 1e6+1;

const int N = 2e5+1;
vi edges[N],cnt(N,0),c(N),saw(N,0),tin(N),tout(N),antitin(N),par(N);

int ans = inf;


vi dad(N),sz(N);
set<int> comps[N];
struct DSU {
    DSU(){};
    DSU(int nn) {
        for (int i=1;i<=nn;i++) {
            comps[i].insert(c[i]);
            dad[i] = i;
            sz[i] = 1;
        }
    }
    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }

    void merge(int a,int b) {
        int x = find(a),y = find(b);
        if (x == y) return;
        if (sz[x] > sz[y]) comps[x].swap(comps[y]);
        for (auto it : comps[x]) comps[y].insert(it);
        comps[x].clear();
        sz[y] = comps[y].size();
        dad[x] = y;
    }
} dsu;

set<int> places[N];
int timer = 1;

void operate(int a,int b) {
    //cout << a sp b << endl;
    while (tin[dsu.find(a)] > tin[b]) {
        int lmao = par[dsu.find(a)];
        //cout << "MRG" sp a sp lmao << '\n';
        dsu.merge(a,lmao);
        a = lmao;
    }
}

void dfs(int node,int p) {
    int old = saw[c[node]];
    saw[c[node]]++;
    tin[node] = timer++;
    par[node] = p;
    antitin[tin[node]] = node;
    for (auto it : edges[node]) {
        if (it != p) dfs(it,node);
    }
    int kirito=saw[c[node]]-old;
    //cout << "NODE" sp node << endl;
    tout[node] = timer-1;
    while (1) {
        auto iter = places[c[node]].lower_bound(tin[node]);
        if (iter == places[c[node]].end() || *iter > tout[node]) break;
        operate(antitin[*iter],node);
        places[c[node]].erase(iter);
    }
    places[c[node]].insert(tin[node]);
    if (kirito == cnt[c[node]]) {
        //cout << "C" sp node sp c[node] sp dsu.find(node) sp sz[dsu.find(node)] << endl;
        ans = min(ans,sz[dsu.find(node)]);
    }
} 

void solve() {
    int n,k;
    cin >> n >> k;
    //st[find(i)] --> i rengini şu ana kadar maintainlemek için mergelemem gereken adamlar
    //cevap: min(st[find(c)].size() when node == lca(c1,c2,c3...))
    for (int i=1;i<n;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for (int i=1;i<=n;i++) {
        cin >> c[i];
        cnt[c[i]]++;
    }
    dsu = DSU(n);
    dfs(1,1);
    cout << ans-1 << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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