Submission #698171

#	Time	Username	Problem	Language	Result	Execution time	Memory
698171		queuedq	족보 (KOI18_family)	C++17	0 / 100	10 ms	14548 KiB

family

#include <bits/stdc++.h>
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

////////////////////////////////////////////////////////////////
const int MN = 303030;
int K, N1, N2;

struct Tree {
  int root, cnt[MN], rep[MN];
  vector<int> adj[MN];

  void set_parent(int u, int p) {
    if (p == 0) root = u;
    else adj[p].push_back(u);
  }

  void dfs(int u) {
    if (u <= K) cnt[u] = 1, rep[u] = u;
    for (auto v: adj[u]) {
      dfs(v);
      cnt[u] += cnt[v];
      rep[u] = rep[v];
    }
  }
};
Tree T1, T2;

// dsu
int par[MN], siz[MN];

void init(int N) {
  for (int i=1; i<=N; i++) par[i] = i, siz[i] = 1;
}

int find(int x) {
  if (par[x] == x) return x;
  return par[x] = find(par[x]);
}

void merge(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  par[y] = x;
  siz[x] += siz[y];
}

int size(int x) {
  return siz[find(x)];
}
// end dsu

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ////////////////////////////////

  cin >> N1 >> N2 >> K;
  for (int u=1, p; u<=N1; u++) { cin >> p; T1.set_parent(u, p); }
  for (int u=1, p; u<=N2; u++) { cin >> p; T2.set_parent(u, p); }

  T1.dfs(T1.root);
  T2.dfs(T2.root);

  vector<array<int, 3>> E;
  for (int u=K+1; u<=N1; u++) E.push_back({T1.cnt[u], u, 1});
  for (int u=K+1; u<=N2; u++) E.push_back({T2.cnt[u], u, 2});
  sort(all(E));

  init(K);
  bool ok = 1;
  for (auto [c, u, t]: E) {
    Tree &T = t == 1 ? T1 : T2;
    for (auto v: T.adj[u]) merge(T.rep[u], T.rep[v]);
    if (size(T.rep[u]) != c) ok = 0;
  }
  cout << (ok ? "YES" : "NO") << endl;

  ////////////////////////////////
  return 0;
}

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