Submission #848277

#	Time	Username	Problem	Language	Result	Execution time	Memory
848277		Plurm	Beech Tree (IOI23_beechtree)	C++17	0 / 100	124 ms	44032 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
  vector<int> dep(N);
  dep[0] = 0;
  vector<set<int>> chs(N);
  vector<int> d1c;
  d1c.resize(M + 1, 0);
  vector<int> d2c;
  d2c.resize(M + 1, 0);
  vector<int> ret;
  ret.resize(N, 1);
  bool flag = true;
  vector<set<int>> ps(M + 1);
  for (int i = 1; i < N; i++) {
    if (P[i] == 0)
      dep[i] = 1;
    else
      dep[i] = 2;
    if (chs[P[i]].count(C[i])) {
      ret[P[i]] = 0;
      flag = false;
    }
    chs[P[i]].insert(C[i]);
    if (dep[i] == 2) {
      d2c[C[i]]++;
      ps[C[i]].insert(P[i]);
    } else {
      d1c[C[i]]++;
    }
  }
  if (!flag)
    ret[0] = 0;
  for (int i = 1; i <= M; i++)
    if (d2c[i] != 0 && d1c[i] == 0)
      ret[0] = 0;
  if (ret[0] == 0)
    return ret;
  // assume d1 is distinct
  set<int> active;
  set<int> activated;
  vector<int> dc;
  dc.resize(M + 1, 0);
  for (int i = 1; i < N; i++) {
    if (dep[i] == 2 && d2c[C[i]] == 1) {
      active.insert(P[i]);
    } else if (dep[i] == 1 && chs[i].empty()) {
      activated.insert(i);
    }
    if (dep[i] == 1)
      dc[C[i]]++;
  }
  int num = 0;
  while (!active.empty()) {
    int cur = *active.begin();
    num++;
    activated.insert(cur);
    active.erase(cur);
    for (int x : chs[cur]) {
      d2c[x]--;
      dc[x]++;
      if (dc[x] <= num) {
        ret[0] = 0;
        return ret;
      }
      ps[x].erase(cur);
      if (d2c[x] == 1) {
        for (int y : ps[x])
          active.insert(y);
      }
    }
  }
  for (int i = 0; i <= M; i++)
    if (dep[i] == 1 && activated.count(i) == 0)
      ret[0] = 0;
  return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12