Submission #1210991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210991		hyakup	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2098 ms	31672 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> &sub ){

  sub.push_back(cur);

  // resp[cur] = true;
  for( auto [viz, cor] : adj[cur] ){
    // mask[cur].push_back(cor);
    dfs( viz, sub );
    // 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);

  for( int i = 0; i < n; i++ ){
    vector<int> sub;
    dfs(i, sub);
    sort( sub.begin(), sub.end() );

    do{
      if( sub[0] != i ) continue;
      vector<int> cont(m + 1);
      bool ok = true;
      for( int i = 1; i < sub.size(); i++ ){
        if( sub[cont[c[sub[i]]]] != p[sub[i]] ) ok = false;
        cont[c[sub[i]]]++; 
      }

      if( ok ){ resp[i] = true; break; }
    }while( next_permutation(sub.begin(), sub.end()) );
  }

  return resp;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 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