Submission #158717

#TimeUsernameProblemLanguageResultExecution timeMemory
158717maruii족보 (KOI18_family)C++14
0 / 100
14 ms14584 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; #define ff first #define ss second int N, M, K; struct G { vector<int> edge[300005]; int sz[300005], rep[300005]; int dfs(int x) { if (x && x <= K) rep[x] = x, sz[x] = 1; for (auto i : edge[x]) rep[x] = dfs(i), sz[x] += sz[i]; return rep[x]; } } t1, t2; int par[300005], sz[300005]; int fnd(int x) { return x == par[x] ? x : par[x] = fnd(par[x]); } void uni(int x, int y) { x = fnd(x), y = fnd(y); if (x == y) return; par[y] = x; sz[x] += sz[y]; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> N >> M >> K; iota(par, par + K + 1, 0); fill(sz, sz + K + 1, 1); for (int i = 1; i <= N; ++i) { int x; cin >> x; t1.edge[x].push_back(i); } for (int i = 1; i <= M; ++i) { int x; cin >> x; t2.edge[x].push_back(i); } t1.dfs(0); t2.dfs(0); vector<pii> vec; for (int i = K + 1; i <= N; ++i) vec.emplace_back(t1.sz[i], i); for (int i = K + 1; i <= M; ++i) vec.emplace_back(t2.sz[i], -i); sort(vec.begin(), vec.end()); for (auto i : vec) { int r; if (i.ss < 0) { i.ss = -i.ss; r = t2.rep[i.ss]; for (auto j : t2.edge[i.ss]) uni(r, t2.rep[j]); } else { r = t1.rep[i.ss]; for (auto j : t1.edge[i.ss]) uni(r, t1.rep[j]); } if (sz[fnd(r)] != i.ff) return !printf("NO"); } printf("YES"); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...