Submission #1241369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241369		mychecksedad	Beech Tree (IOI23_beechtree)	C++17	0 / 100	12 ms	23924 KiB

beechtree

#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
const int N = 2e5+100;

int s[N], m;
vi T[N], S[N], C;
set<int> TT[N];
vector<pii> g[N];
vi res;

bool check_cover(vi &x, vi &y){
  for(int u: y){
    int pos = lower_bound(all(x), u) - x.begin();
    if(pos < (int)x.size() && x[pos] == u) continue;
    return false;
  }
  return true;
}

void dfs(int v){
  bool ok = true;
  vi col;
  s[v] = 1;
  if(g[v].empty()){
    res[v] = 1;
    return;
  }
  S[v].pb(v);
  int big = -1;
  for(auto [u, cl]: g[v]){
    dfs(u);
    for(int x: S[u]) S[v].pb(x);
    TT[u].insert(cl);
    if(big == -1 || s[u] > s[big]) big = u;
    s[v] += s[u];
    if(res[u] == 0){
      ok = false;
    }
    col.pb(cl);
  }
  if(!ok){
    res[v] = 0;
    return;
  }

  int sz = col.size();
  sort(all(col));
  col.erase(unique(all(col)), col.end());
  T[v] = col;
  if((int)col.size() < sz){
    res[v] = 0;
    return;
  }


  TT[v].swap(TT[big]);
  for(auto [u, cl]: g[v]){
    if(u != big){
      for(int x: TT[u]) TT[v].insert(x);
    }
  }

  vector<vi> CL(m + 1);

  for(int x: TT[v]){
    for(int u: S[v]){
      if(C[u] == x)
        CL[x].pb(u);
    }
    sort(all(CL[x]));
  }
  sort(all(CL), [&](const vi &x, const vi &y){
    return x.size() > y.size();
  });
  bool fine = true;
  for(int i = 1; i < (int) CL.size(); ++i){
    if(!check_cover(CL[i - 1], CL[i])){
      fine = false;
      break;
    }
  }
  if(!fine){
    res[v] = 0;
    return;
  }
  res[v] = 1;
  return;
}

std::vector<int> beechtree(int n, int mm, std::vector<int> P, std::vector<int> CC)
{
  m = mm;
  C = CC;
  for(int i = 0; i < n; ++i) T[i].clear(), g[i].clear();
  res.clear();
  res.resize(n);

  for(int i = 1; i < n; ++i) g[P[i]].pb({i, C[i]});

  dfs(0);

  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