Submission #1241370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241370		dosts	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2096 ms	30272 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;

const int LIM = 2e5+1;
vector<pii> edges[LIM];
vi ans(LIM,0),C,P;
vi stuf;

void dfss(int node) {
    stuf.push_back(node);
    for (auto it : edges[node]) dfss(it.ff);
}

vi ctr,pos;
int N;
bool check(int node) {
    stuf.clear();
    dfss(node);
    vi perm(stuf.size());
    iota(all(perm),0ll);
    do {
        ctr.assign(N,0);
        pos.assign(N,-1);
        int fl = 1;
        for (int j = 0;j<stuf.size();j++) {
            int nd = stuf[perm[j]];
            if (nd != node && (pos[P[nd]] == -1 || ctr[C[nd]] != pos[P[nd]])) {
                fl = 0;
            }
            pos[stuf[perm[j]]] = j;
            if (nd != node) ctr[C[nd]]++;
        }
        if (fl) return true;
    }while (next_permutation(all(perm)));
    return false;
}


void dfs(int node) {
    ans[node] = check(node);
    for (auto it : edges[node]) {
        dfs(it.ff);
    }
}

std::vector<int> beechtree(int N_, int M, std::vector<int> P_, std::vector<int> C_)
{
    N = N_;
    P = P_,C = C_;
    ans.assign(N_,0);
    for (int i = 0;i<N;i++) edges[i].clear(); 
    vi v;
    for (auto it : C) v.push_back(it);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    for (auto& it : C) it = lower_bound(all(v),it)-v.begin();
    for (int i = 1;i<N;i++) {
        edges[P[i]].push_back({i,C[i]});
    }
    dfs(0);
    return ans;
}

• 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