#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |