Submission #1241352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241352		mychecksedad	Beech Tree (IOI23_beechtree)	C++17	22 / 100	80 ms	62020 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];
vi T[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;
  }
  for(auto [u, cl]: g[v]){
    dfs(u);
    s[v] += s[u];
    if(res[u] == 0){
      ok = false;
    }
    col.pb(cl);
  }
  if(!ok){
    res[v] = 0;
    return;
  }
  if(v != 0){
    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;
    }
    int id = -1;
    for(auto [u, col]: g[v]){
      if(s[u] > 1){
        if(id == -1)
          id = u;
        else id = -2;
      }
    }
    if(id == -2) res[v] = 0;
    else if(id == -1) res[v] = 1;
    else{
      if(check_cover(T[v], T[id])){
        res[v] = 1;
      }else{
        res[v] = 0;
      }
    }
  }else{
    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;
    }
    sort(all(g[v]), [&](const pii &x, const pii &y){
      return (int)T[x.ff].size() > (int)T[y.ff].size();
    });
    vector<vi> S;
    S.pb(T[v]);
    for(auto [u, cl]: g[v]) S.pb(T[u]);
    for(int i = 1; i < (int) S.size(); ++i){
      if(!check_cover(S[i-1], S[i])){
        res[v] = 0;
        return;
      }
    }
    res[v] = 1;
  }
}

std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> C)
{
  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: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 8 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12