Submission #1058505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058505		mc061	Beech Tree (IOI23_beechtree)	C++17	0 / 100	24 ms	7284 KiB

beechtree

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

const int N = 1e3+1;

int cnt[N]={};
vector<int> tree[N];
int c[N]={};
int p[N]={};
int depth[N]={};

map<int, int> inside[1001];
map<int, int> supposed[1001];

bool cmp(map<int, int>& mp1, map<int, int>& mp2) {
    if (mp1.size() != mp2.size()) return false;
    for (auto it = mp1.begin(); it != mp1.end(); ++it) {
        int key = it->first;
        auto it2 = mp2.lower_bound(key);
        if (it2 == mp2.end() || it2->first != key || it2->second != it->second) return false;
    }
    return true;
}


vector<vector<int>> by_depths(N);
bool ck(vector<int> sub) {
    memset(cnt, 0, sizeof(cnt));
    int sz = sub.size();
    if (sz == 1) return true;
    vector<int> depths(sz, 0);
    vector<bool> matched(sz, false);
    vector<int> now(sz, -1);
    for (int i = 0; i < sz; ++i) {
        inside[i].clear();
        depths[i] = depth[sub[i]];
    }
    for (int i = depths[0]; i <= depths.back(); ++i) by_depths[i].clear();
    for (int i = 0; i < sz; ++i) by_depths[depths[i]].push_back(sub[i]);
    for (int i = 1; i < sz; ++i) {
        int par = cnt[c[sub[i]]];
        inside[par][c[sub[i]]]++;
        if (depths[par] != depth[sub[i]]-1) return false;
        cnt[c[sub[i]]]++;
    }

    for (int i = 0; i < sz; ++i) {
        for (int j = 0; j < sz; ++j) {
            if (matched[j]) continue;
            if (depths[i] == depths[j] && cmp(inside[i], supposed[sub[j]])) {
                matched[j] = true;
                now[i] = j;
                break;
            }
        }
        if (now[i] == -1) return false;
    }
    for (int i = 1; i < sz; ++i) {
        cnt[c[sub[i]]]--;
    }

    for (int i = 1; i < sz; ++i) {
        int par = cnt[c[now[i]]];
        if (p[now[i]] != now[par]) return false;
        cnt[c[now[i]]]++;
    }
    return true;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
    for (int i = 1; i < N; ++i) {
        p[i] = P[i];
        tree[i].push_back(p[i]);
        tree[p[i]].push_back(i);
        c[i] = C[i];
    }
    auto dfs = [&] (auto&& self, int v, int d=0) -> void {
        depth[v] = d;
        for (int u : tree[v]) if (u != p[v]) {
            self(self, u, d+1);
        }
    };
    dfs(dfs, 0);
    vector<int> res(N);
    for (int i = 0; i < N; ++i) {
        for (int u : tree[i]) if (u != p[i]) {
            supposed[i][c[u]]++;
        }
    }
    for (int i = 0; i < N; ++i) {
        vector<int> sub = {};
        auto bfs = [&] (int s) -> void {
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                sub.push_back(v);
                for (int u : tree[v]) if (u != p[v]) {
                    q.push(u);
                }
            }
        };
        bfs(i);
        res[i] = ck(sub);
    }
    return res;
}

• 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