Submission #329975

#TimeUsernameProblemLanguageResultExecution timeMemory
329975oolimry족보 (KOI18_family)C++14
0 / 100
9 ms14444 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() using namespace std; typedef pair<int,int> ii; int n1, n2, K; vector<int> child[2][300005]; int num[2][300005]; int rep[2][300005]; struct check{ int num, u, t; }; vector<check> stuff; void dfs(int t, int u){ if(num[t][u] != 0) return; if(u <= K){ num[t][u] = 1; rep[t][u] = u; } else{ for(int v : child[t][u]){ dfs(t, v); num[t][u] += num[t][v]; rep[t][u] = rep[t][v]; } if(num[t][u] > 1) stuff.push_back({num[t][u], u, t}); } } int p[300005]; int sz[300005]; int findSet(int u){ if(p[u] == u) return u; else return p[u] = findSet(p[u]); } void unionSet(int u, int v){ u = findSet(u), v = findSet(v); if(u == v) return; if(u&1) swap(u,v); p[u] = v; sz[v] += sz[u]; } int getSz(int u){ return sz[findSet(u)]; } int main(){ cin >> n1 >> n2 >> K; for(int i = 1;i <= n1;i++){ int a; cin >> a; child[0][a].push_back(i); } for(int i = 1;i <= n2;i++){ int a; cin >> a; child[1][a].push_back(i); } for(int i = 1;i <= n1;i++) dfs(0, i); for(int i = 1;i <= n2;i++) dfs(1, i); for(int i = 1;i <= K;i++){ p[i] = i; sz[i] = 1; } sort(all(stuff), [&](check a, check b){ return a.num < b.num; }); for(check C : stuff){ for(int v : child[C.t][C.u]){ unionSet(rep[C.t][C.u], rep[C.t][v]); } if(getSz(rep[C.t][C.u]) != C.num){ cout << "NO"; return 0; } } cout << "YES"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...