Submission #1242521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242521		bangan	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2096 ms	73028 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ALL(a) a.begin(), a.end()

const int MXN = 200200;

int n;
int m;
vector<int> p;
vector<int> c;
vector<int> adj[MXN];

bool is_subset(vector<int> a, vector<int> b) {
    set<int> all;
    for (int x : b) all.insert(c[x]);
    for (int x : a) if (!all.contains(c[x])) return false;
    return true;
}

bool is_unq(vector<int> a) {
    sort(ALL(a), [&](int x, int y) {
        return c[x]<c[y];
    });
    for (int i=0; i+1 < a.size(); i++) if (c[a[i]] == c[a[i+1]]) return false;
    return true;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    n = N;
    m = M;
    p = P;
    c = C;
    for (int i=1; i<n; i++) adj[p[i]].pb(i);

    vector<int> ans(n);
    auto dfs = [&](auto self, int v) -> vector<int> {
        vector<vector<int>> vec;
        for (int u : adj[v]) {
            vec.pb({});
            auto res = self(self, u);
            for (int it : res) if (it != u) vec.back().pb(it);
        }

        sort(ALL(vec), [&](auto x, auto y) {
            return x.size() < y.size();
        });

        vec.pb(adj[v]);
    
        ans[v] = 1;
        for (int u : adj[v]) if (ans[u]==0) ans[v]=0;
        if (!is_unq(vec.back())) ans[v]=0;
        for (int i=0; i+1 < vec.size(); i++) if (!is_subset(vec[i], vec[i+1])) ans[v]=0;
        
        vector<int> ret;
        for (auto x : vec) for (auto y : x) ret.pb(y);
        return ret;
    };
    dfs(dfs, 0);

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 9 / 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