Submission #1004652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004652		MilosMilutinovic	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2035 ms	43852 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<vector<int>> ch(n);
  for (int i = 1; i < n; i++) {
    ch[p[i]].push_back(i);
  }
  vector<vector<int>> my(n);
  for (int i = 0; i < n; i++) {
    for (int j : ch[i]) {
      my[i].push_back(c[j]);
    }
  }
  vector<bool> diff(n);
  for (int i = 0; i < n; i++) {
    set<int> st(my[i].begin(), my[i].end());
    diff[i] = (st.size() == my[i].size());
  }
  vector<int> tin(n);
  vector<int> tout(n);
  int T = 0;
  function<void(int)> Dfs = [&](int v) {
    tin[v] = ++T;
    for (int u : ch[v]) {
      Dfs(u);
    }
    tout[v] = T;
  };
  Dfs(0);
  auto IsAnc = [&](int x, int y) {
    return tin[x] <= tin[y] && tout[y] <= tout[x];
  };
  auto IsSubset = [&](vector<int> a, vector<int> b) {
    set<int> st(a.begin(), a.end());
    for (int i : b) {
      if (st.find(i) == st.end()) {
        return false;
      }
    }
    return true;
  }; 
  auto NoIntersect = [&](vector<int> a, vector<int> b) {
    set<int> st;
    for (int i : a) {
      st.insert(i);
    }
    for (int i : b) {
      st.insert(i);
    }
    return st.size() == a.size() + b.size();
  };
  vector<int> res(n);
  for (int v = 0; v < n; v++) {
    bool ok = true;
    vector<int> ver;
    for (int i = 0; i < n; i++) {
      if (IsAnc(v, i)) {
        ver.push_back(i);
      }
    }
    for (int i : ver) {
      ok &= diff[i];
    }
    for (int i : ver) {
      if (i == v) {
        continue;
      }
      ok &= IsSubset(my[p[i]], my[i]);
    }
    for (int i : ver) {
      for (int j : ver) {
        if (IsAnc(i, j) || IsAnc(j, i)) {
          continue;
        }
        ok &= NoIntersect(my[i], my[j]);
      }
    }
    res[v] = ok;
  }
  return res;
}

• 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