제출 #1210991

#제출 시각아이디문제언어결과실행 시간메모리
1210991hyakupBeech Tree (IOI23_beechtree)C++20
9 / 100
2098 ms31672 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...