Submission #1244446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244446		quannnguyen2009	족보 (KOI18_family)	C++20	0 / 100	8 ms	14404 KiB

family

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 3e5+5, mod = 1e9+7, inf = 1e18;

int n[2], k;
vector<int> adj[2][N];
int rt[2][N];
int sz[2][N];

void dfs(int u, int id) {
    sz[id][u] = 1;
    if (sz(adj[id][u])==0) rt[id][u] = u;
    for (int v: adj[id][u]) {
        dfs(v, id);
        rt[id][u] = rt[id][v];
        sz[id][u] += sz[id][v];
    }
}

struct DSU {
    int par[N], sz[N];
    void init(int n) {
        iota(par, par+n+1, 0);
        fill(sz, sz+n+1, 1);
    }
    int find(int u) {
        if (par[u] == u) return u;
        return par[u] = find(par[u]);
    }
    bool join(int u, int v) {
        u = find(u); v = find(v);
        if(u == v) return 0;
        if(sz[u]<sz[v]) swap(u, v);
        par[v] = u; sz[u] += sz[v];
        return 1;
    }     
    int csz(int u) {return sz[find(u)];}
    bool check(int u, int v) {
        return find(u)==find(v);
    }
} DSU;

struct Item {
    int sz, id, u;
    bool operator<(Item& o) const {
        return sz<o.sz;
    }
};

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n[0] >> n[1] >> k;
    for (int j=0; j<=1; j++) {
        for (int i=1; i<=n[j]; i++) {
            int x; cin >> x;
            adj[j][x].pb(i);
        }
    }
    dfs(0, 0);
    dfs(0, 1);
    vector<Item> v;
    for (int j=0; j<2; j++) {
        for (int i=k+1; i<=n[j]; i++) v.pb({sz[j][i], j, i});
    }
    sort(all(v));
    DSU.init(k);
    for (auto it: v) {
        int sz = it.sz, id = it.id, u = it.u;
        for (int it_: adj[id][u]) DSU.join(rt[id][it_], rt[id][u]);
        if (DSU.csz(rt[id][u])>sz) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41