Submission #540341

#	Time	Username	Problem	Language	Result	Execution time	Memory
540341		PixelCat	Capital City (JOI20_capital_city)	C++14	11 / 100	1897 ms	524288 KiB

capital_city

/* code by the cute ~~Dengdualang~~ PixelCat owo */
/*     as cute as nacho neko (aka. my wife)!     */

/*     Nhade stay for a night here               */
/*     183234 deng deng deng pixelcat oops       */
/*     (yang wang yesu)*2                        */
/*     ^ some weird stuff. nvm =w=               */

#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using LLL = __int128_t;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(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 Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(998244353)
// #define MOD (int)((LL)1e9 + 7)
#define INF (int)(4e18)  // 9e18
#define EPS (1e-6)

#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

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p >>= 1;
        b = b * b % mod;
    }
    return ans;
}
int fpow(int b, int p) {
    return fpow(b, p, MOD);
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// mt19937_64 rng(
//     chrono::steady_clock::now().time_since_epoch().count());

const int MAXN=200020;
const int lg=19;

vector<int> tr[MAXN];
int par[MAXN][20];
int dep[MAXN];

int cid[MAXN]; // city number
int crt[MAXN]; // root for each city

struct Node{
    vector<Node*> adj;
    vector<Node*> rev;
    int vis;
    bool real;
    Node():adj(),vis(0),real(0){}
};
Node up[MAXN][20];
Node ct[MAXN];

inline void link(Node &a,Node &b){
    a.adj.eb(&b);
    b.rev.eb(&a);
    // cerr<<&a<<" "<<&b<<"\n";
}

void buildLCA(int n){
    auto dfs = [&](auto fdfs, int x, int p, int d) -> void{
        dep[x]=d;
        par[x][0]=p;
        link(up[x][0],ct[cid[x]]);
        link(ct[cid[x]],up[x][0]);
        for(auto &i:tr[x]) if(i!=p){
            fdfs(fdfs,i,x,d+1);
        }
    };
    dfs(dfs,1,1,1);
    For(j,1,lg) For(i,1,n){
        par[i][j]=par[par[i][j-1]][j-1];
        link(up[i][j],up[i][j-1]);
        link(up[i][j],up[par[i][j-1]][j-1]);
    }
}
int getLCA(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    int dif=dep[a]-dep[b];
    Forr(j,lg,0) if(dif&(1<<j)){
        a=par[a][j];
    }
    Forr(j,lg,0) if(par[a][j]!=par[b][j]){
        a=par[a][j];
        b=par[b][j];
    }
    if(a!=b) a=par[a][0];
    return a;
}
void link(int a,int r){
    int dif=dep[a]-dep[r]+1;
    int k=a;
    Forr(j,lg,0) if(dif&(1<<j)){
        link(up[a][0],up[k][j]);
        k=par[k][j];
    }
}

int buildSCC(int n){
    vector<Node*> st;
    auto dfs1=[&](auto dfs,Node* nd)->void{
        nd->vis=-1;
        for(auto &i:nd->rev) if(i->vis==0){
            dfs(dfs,i);
        }
        st.eb(nd);
    };
    For(i,1,n) if(ct[i].vis==0) dfs1(dfs1,ct+i);
    // cerr<<st<<"\n";
    int sccid;
    int now;
    int ans=INF;
    auto dfs2=[&](auto dfs,Node* nd)->void{
        // cerr<<nd<<" "<<sccid<<"\n";
        nd->vis=sccid;
        now+=nd->real;
        for(auto &i:nd->adj){
            if(i->vis==-1) dfs(dfs,i);
            else if(i->vis!=sccid) now=INF;
        }
    };
    sccid=0;
    while(sz(st)){
        auto x=st.back(); st.pop_back();
        if(x->vis!=-1) continue;
        sccid++;
        now=0;
        dfs2(dfs2,x);
        chmin(ans,now);
    }
    return ans;
}

int32_t main() {
    NYA();
    // nyaacho >/////<
    // miku sama bless me >/////<
    int n,k; cin>>n>>k;
    For(i,1,n-1){
        int a,b; cin>>a>>b;
        tr[a].eb(b);
        tr[b].eb(a);
    }
    For(i,1,n) cin>>cid[i];
    buildLCA(n);
    For(i,1,n){
        int &c=cid[i];
        if(crt[c]==0) crt[c]=i;
        else crt[c]=getLCA(crt[c],i);
    }
    For(i,1,n) link(i,crt[cid[i]]);
    For(i,1,k) ct[i].real=1;

    // cerr<<"\n";
    // For(i,1,n) For(j,0,lg){
    //     cerr<<(par[i][j])<<" \n"[j==lg];
    // }
    // cerr<<"\n";
    // For(i,1,n) For(j,0,lg){
    //     cerr<<&(up[i][j])<<" \n"[j==lg];
    // }
    // cerr<<"\n";
    // For(i,1,k) cerr<<ct+i<<" \n"[i==k];
    // cerr<<"\n";

    cout<<buildSCC(k)-1<<"\n";
    return 0;
}

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