Submission #1232866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232866		antonn	Beech Tree (IOI23_beechtree)	C++20	9 / 100	218 ms	101380 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int n, m;
vector<int> g[N];
int col[N], ok[N], par[N], sz[N];
set<int> all;
map<int, int> mp[N];

void dfs(int u) {
    sz[u] = 1;
    for (auto v : g[u]) {
        dfs(v);
        sz[u] += sz[v];
    }
    if (g[u].size() == 0) {
        ok[u] = 1;
        return;
    }
    if (u != 0) {
        set<int> children;
        for (auto v : g[u]) children.insert(col[v]);
        if (children.size() == g[u].size()) ok[u] = 1;
    } else {
        set<int> children;
        for (auto v : g[u]) children.insert(col[v]);
        if (children.size() != g[u].size()) ok[u] = 0;
        for (auto v : g[u]) if (ok[v] == 0) ok[u] = 0;
        if (children.size() != all.size()) ok[u] = 0;
        // ----------------------
        
        int cnt = 0;
        for (auto v : g[u]) if (g[v].size() > 0) ++cnt;
        set<int> down;
        bool aux = 1;
        for (auto v : g[u]) for (auto x : g[v]) mp[v][col[x]]++;
        
        sort(g[u].begin(), g[u].end(), [&](int u, int v) {
            return sz[u] > sz[v];
        });
        
        if (!ok[u]) return;
        
        map<int, int> fr;
        int here = 0;
        for (auto v : g[u]) {
            int x = -1;
            for (auto it : mp[v]) {
                if (x == -1) {
                    x = it.second;
                    here += it.second;
                    assert(it.second == 1);
                }
                
                fr[it.first] += it.second;
                if (fr[it.first] != here) {
                    ok[u] = 0;
                }
                aux &= it.second == x; 
            }
        }
        
        
        if (cnt > 1 && !aux) ok[u] = 0;
        
    }
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    n = N;
    m = M;
    for (int i = 0; i < n; ++i) {
        par[i] = P[i];
        if (i > 0) {
            g[P[i]].push_back(i);
        }
    }
    ok[0] = 1;
    map<int, int> f;
    for (int i = 0; i < n; ++i) {
        col[i] = C[i];
    }
    for (int i = 1; i < n; ++i) {
        f[col[i]]++;
        all.insert(col[i]);
    }
    dfs(0);
    vector<int> ret(n);
    for (int i = 0; i < n; ++i) ret[i] = ok[i];
    return ret; 
}

• 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