Submission #1210984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210984		hyakup	Beech Tree (IOI23_beechtree)	C++20	22 / 100	74 ms	48808 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

#define bug(x) cout << #x << " " << x << endl;

vector<vector<pair<int, int>>> adj;
vector<vector<int>> mask;
vector<int> ruim;

bool is_supermask( vector<int> &a, vector<int> &b ){
  int p = 0;
  for( int x : a ){
    if( p == b.size() ) break;
    if( b[p] == x ) p++;
  }
  return p == b.size();
}

void dfs( int cur, vector<int> &resp ){

  resp[cur] = true;
  for( auto [viz, cor] : adj[cur] ){
    mask[cur].push_back(cor);
    dfs( viz , resp );
    resp[cur] &= resp[viz];
  }

  sort( mask[cur].begin(), mask[cur].end() );
  for( int i = 1; i < mask[cur].size(); i++ ) if( mask[cur][i] == mask[cur][i - 1] ) resp[cur] = false;

  sort( adj[cur].begin(), adj[cur].end(), [&]( pair<int, int> a, pair<int, int> b ){
    return mask[a.first].size() < mask[b.first].size();
  });

  for( int i = 1; i < adj[cur].size(); i++ )
    if( !is_supermask(mask[adj[cur][i].first], mask[adj[cur][i - 1].first] ) ) resp[cur] = false;

  if( !adj[cur].empty() && !is_supermask(mask[cur], mask[adj[cur].back().first]) ) resp[cur] = false;


}

vector<int> beechtree(int n, int m, vector<int> p, vector<int> c ){
  adj.resize(n);
  mask.resize(n);
  ruim.resize(n);
  for( int i = 1; i < n; i++ ) adj[p[i]].push_back({ i, c[i] });

  vector<int> resp(n);
  dfs( 0, resp );
  return resp;
}

• 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