Submission #1335388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335388		nerrrmin	Beech Tree (IOI23_beechtree)	C++20	0 / 100	1 ms	344 KiB

beechtree

#include "beechtree.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
int n, m, p[maxn], c[maxn];

vector < int > sub[maxn], g[maxn];
void dfs(int beg)
{
    sub[beg].pb(beg);
    for (auto nb: g[beg])
    {
        dfs(nb);
        for (auto x: sub[nb])
            sub[beg].pb(x);
    }
}
int curr_root, sz, used[maxn], a[maxn];

map < int, int > mp;
int is;
void check()
{
    mp.clear();
    int no = 0;
    for (int i = 0; i < sz; ++ i)
    {
        if(i != 0)
        {
            int fi = mp[c[a[i]]];
            int exp_par = p[a[i]];
            int par = a[fi];
            if(exp_par != par)no = 1;
        }
        mp[c[i]] ++;
    }
    if(!no)is ++;
}
void gen(int pos)
{
    if(pos == sz)
    {
        check();
        return;
    }
    for (int i = 0; i < (int)sub[curr_root].size(); ++ i)
    {
        if(used[i])
        {
            continue;
        }
        used[i] = 1;
        a[pos] = i;
        gen(pos + 1);
        used[i] = 0;
    }
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n = N;
    m = M;
    for (int i = 0; i < n; ++ i)
    {
        p[i] = P[i];
        c[i] = C[i];
        if(p[i] != -1)g[p[i]].pb(i);
    }
    vector < int > ans;
    for (int root = 0; root < n; ++ root)
    {
        curr_root = root;
        sz = sub[root][0];
        used[0] = 1;
        a[0] = root;
        is = 0;
        gen(1);
        used[0] = 0;
        ans.pb(is);
    }
    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