Submission #1192713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192713		Amr	Beech Tree (IOI23_beechtree)	C++20	0 / 100	26 ms	5192 KiB

beechtree

#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define F first
#define S second

vector<ll> vec;
ll tim = 0;
ll cnt[502];
ll a[502];
ll childs[502];
vector<ll> v[10];
vector<int> p;
void dfs(ll x)
{
    childs[x] = 1;
    for(int i = 0; i < v[x].sz; i++)
    {
        if(v[x][i]==p[i]) continue;
        dfs(v[x][i]);
        childs[x]+=childs[v[x][i]];
    }
}

void dfs2(ll x)
{
    a[tim++] = x;
    for(int i = 0; i < v[x].sz; i++)
    {
        if(v[x][i]!=p[i]) dfs2(v[x][i]);
    }
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    p = P;
    vector<int> ans(N,0);
    for(int i = 1; i < N; i++) v[P[i]].push_back(i);
    dfs(0);
    for(int i = 0; i < N; i++)
    {
        vec.clear(); vec.push_back(0);
        for(int j = 1; j < childs[i]; j++) vec.push_back(j);
        do{
                bool ok = 1; tim = 0;dfs2(i);
                for(int j = 1; j < vec.sz; j++)
                {
                    if(a[cnt[C[a[j]]]]!=P[a[j]]) ok = 0;
                    //if(i==0) cout << cnt[C[a[j]]] << " ";
                    cnt[C[a[j]]]++;
                }
                for(int j = 1; j < vec.sz; j++) cnt[C[a[j]]]--;
                if(ok)ans[i] = 1;
        }while(next_permutation(vec.begin()+1, vec.end()));
    }
    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