Submission #1241394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241394		SalihSahin	Beech Tree (IOI23_beechtree)	C++20	0 / 100	2098 ms	33452 KiB

beechtree

#include "bits/stdc++.h"
#include "beechtree.h"
#define pb push_back
using namespace std;

const int N = 2e5 + 5;
vector<pair<int, int> > ch[N];

bool comp(int a, int b){
   return (ch[a].size() > ch[b].size());
}

vector<int> perm;
vector<pair<int, int> > edges;

void dfs(int node){
   perm.pb(node);
   for(auto itr: ch[node]){
      edges.pb(itr);
      dfs(itr.first);
   }
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
   for(int i = 0; i < N; i++){
      ch[i].clear();
   }

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

   vector<int> ans(N, 0);
   for(int i = 0; i < N; i++){
      perm.clear();
      edges.clear();
      dfs(i);

      sort(perm.begin(), perm.end(), comp);
      if(perm[0] != i) continue;

      vector<int> cnt(M+1), pos(N);
      for(int j = 0; j < perm.size(); j++){
         pos[perm[j]] = j;
      }

      bool ok = 1;
      for(int j = 1; j < perm.size(); j++){
         if(pos[P[perm[j]]] != cnt[C[perm[j]]]){
            ok = 0;
         }
         cnt[C[perm[j]]]++;
      }
      /*
      cout<<i<<" icin perm: ";
      for(auto itr: perm){
         cout<<itr<<" ";
      }
      cout<<endl;
      */

      if(ok) ans[i] = 1;
      else ans[i] = 0;
   }

   return ans;
}

• 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