oj.uz

Submission #848277

# Submission time Handle Problem Language Result Execution time Memory
848277 2023-09-11T23:50:25 Z Plurm Beech Tree (IOI23_beechtree) C++17
0 / 100
 124 ms 44032 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 124 ms 44032 KB 2nd lines differ - on the 2nd token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -