Submission #713046

#	Time	Username	Problem	Language	Result	Execution time	Memory
713046		PixelCat	Capital City (JOI20_capital_city)	C++14	100 / 100	1146 ms	48700 KiB

capital_city

/* nya */
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
#define MOD (int)(1000000007)
// #define MOD (int)(998244353)
using namespace std;
using LL = long long;
// using LLL = __int128_t;
using pii = pair<int, int>;
 
#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#endif

const int MAXN = 200020;
mt19937_64 rng(48763);

vector<int> adj[MAXN];
int vis[MAXN];  // -1 for expired nodes

int par[MAXN];
int ssz[MAXN];

int city[MAXN];  // town -> city
vector<int> town[MAXN];  // city -> towns
int vist[MAXN];

int dfs(int n, int p, int tag) {
    vis[n] = tag;
    par[n] = p;
    int sz = 1;
    for(auto &i:adj[n]) if(vis[i] != -1 && vis[i] != tag) {
        sz += dfs(i, n, tag);
    }
    ssz[n] = sz;
    return sz;
}

// {size, index}
pii cent(int n, int p, int N) {
    pii res = {INF, -1};
    int mx = 0;
    for(auto &i:adj[n]) if(i != p && vis[i] >= 0) {
        res = min(res, cent(i, n, N));
        mx = max(mx, ssz[i]);
    }
    mx = max(mx, N - ssz[n]);
    res = min(res, pii(mx, n));
    return res;
}

int nya(int n, int siz) {
    int tag = rng();
    n = cent(n, n, siz).S;
    dfs(n, n, tag);
    
    queue<int> que;
    int res = 0;
    
    auto mark = [&](int t) {
        // cout << "mark: " << t << "\n";
        if(vis[t] != (~tag) && vis[t] != tag) return false;
        while(vis[t] == tag) {
            vis[t] = (~tag);
            if(vist[city[t]] != tag) {
                vist[city[t]] = tag;
                que.emplace(city[t]);
            }
            if(t == n) break;
            t = par[t];
        }
        return true;
    };
    mark(n);
    while(!que.empty()) {
        int c = que.front(); que.pop();
        // cout << "city: " << c << "\n";
        res++;
        for(auto &i:town[c]) if(vis[i] != (~tag)) {
            if(!mark(i)) {
                res = INF;
                break;
            }
        }
    }

    vis[n] = -1;
    for(auto &i:adj[n]) if(vis[i] != -1) {
        res = min(res, nya(i, dfs(i, i, rng())));
    }
    return res;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // OAO
    int n, m; cin >> n >> m;
    For(i, 1, n - 1) {
        int a, b; cin >> a >> b;
        adj[a].eb(b);
        adj[b].eb(a);
    }
    For(i, 1, n) {
        cin >> city[i];
        town[city[i]].eb(i);
    }
    dfs(1, 1, 49);
    cout << (nya(1, n) - 1) << "\n";
    return 0;
}

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