제출 #1241407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241407		SalihSahin	Beech Tree (IOI23_beechtree)	C++20	0 / 100	3 ms	4936 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 comp1(int a, int b){
   if(ch[a].size() == ch[b].size()) return (a < b);
   else return (ch[a].size() > ch[b].size());
}

bool comp2(int a, int b){
   if(ch[a].size() == ch[b].size()) return (a > b);
   else 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);
      vector<int> perm2 = perm;

      sort(perm.begin(), perm.end(), comp1);
      sort(perm2.begin(), perm2.end(), comp2);

      if(perm[0] != i) continue;

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

      bool ok = 1;
      for(int j = 1; j < perm.size(); j++){
         if(min(pos[P[perm[j]]], pos2[P[perm[j]]]) > cnt[C[perm[j]]] || max(pos[P[perm[j]]], pos2[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