oj.uz

Submission #698174

# Submission time Handle Problem Language Result Execution time Memory
698174 2023-02-12T18:50:21 Z queuedq None (KOI18_family) C++17
0 / 100
 8 ms 14548 KB 
#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];

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

void merge(int x, int y) {
  assert(1 <= x && x <= K);
  assert(1 <= y && y <= K);
  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++) if (T1.adj[u].size() > 0) E.push_back({T1.cnt[u], 1, u});
  for (int u=K+1; u<=N2; u++) if (T2.adj[u].size() > 0) E.push_back({T2.cnt[u], 2, u});
  sort(all(E));

  for (int i=1; i<=K; i++) par[i] = i, siz[i] = 1;
  bool ok = 1;
  for (auto [c, t, u]: 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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Incorrect 8 ms 14548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Incorrect 8 ms 14548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Incorrect 8 ms 14548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Incorrect 8 ms 14548 KB Output isn't correct
3 Halted 0 ms 0 KB -