제출 #1241486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241486		mychecksedad	Beech Tree (IOI23_beechtree)	C++17	0 / 100	9 ms	19016 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, par;
vector<pii> g[N];
vi res, G[N];

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;
    S[v].pb(v);
    return;
  }

  int big = -1;
  for(auto [u, cl]: g[v]){
    dfs(u);

    G[v].pb(cl);

    col.pb(cl);

    for(int x: S[u]) S[v].pb(x);
    
    if(big == -1 || s[u] > s[big]) big = u;
   
    s[v] += s[u];


    if(res[u] == 0){
      ok = false;
    }
  }
  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;
  }

  vector<vi> pt;
  for(int x: S[v]){
    pt.pb(G[x]);
  }
  sort(all(pt), [&](const vi &x, const vi &y){
    return x.size() > y.size();
  });

  for(int i = 1; i < pt.size(); ++i){
    if(!check_cover(pt[i - 1], pt[i])){
      res[v] = 0;
      return;
    }
  }
  res[v] = 1;
}

std::vector<int> beechtree(int n, int mm, std::vector<int> P, std::vector<int> CC)
{
  m = mm;
  par = P;
  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