Submission #1218428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218428		vanea	Beech Tree (IOI23_beechtree)	C++20	100 / 100	421 ms	124620 KiB

beechtree

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

const int mxN = 2e5+10;
const int INF = 1e9+10;

int sz[mxN];
bool pos[mxN];
set<array<int, 2>> srt[mxN];
map<int, vector<int>> col[mxN];

bool check(int v, int u) {
    for(auto [c, vec] : col[v]) {
        auto it = col[u].find(c);
        if(it == col[u].end() || sz[vec[0]] > sz[it->second[0]]) return false;
    }
    return true;
}

bool add(set<array<int, 2>> &srt, array<int, 2> p) {
    auto [it, st] = srt.insert(p);
    bool result = true;
    if(it != srt.begin()) {
        result &= check((*prev(it))[1], (*it)[1]);
    }
    if(next(it) != srt.end()) {
        result &= check((*it)[1], (*next(it))[1]);
    }
    return result;
}

int dfs(int node) {
    sz[node] = 1;
    pos[node] = true;
    for(auto [c, v] : col[node]) {
        pos[node] &= (v.size() == 1);
        for(auto it : v) {
            int nxt = dfs(it);
            if(nxt == -1) pos[node] = false;
            else {
                sz[node] += nxt;
            }
            if(pos[node]) {
                if(srt[it].size() > srt[node].size()) swap(srt[it], srt[node]);
                for(auto it1 : srt[it]) {
                    pos[node] &= add(srt[node], it1);
                }
            }
        }
    }
    pos[node] &= add(srt[node], {sz[node], node});
    return pos[node] ? sz[node] : -1;
}

vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) {
    for(int i = 1; i < n; i++) {
        int p = P[i], c = C[i];
        if(!col[p].count(c)) {
            col[p][c] = vector<int>();
        }
        col[p][c].push_back(i);
    }
    dfs(0);
    vector<int> ans(n);
    for(int i = 0; i < n; i++) {
        ans[i] = pos[i];
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 12 / 12
• Subtask 8: 17 / 17
• Subtask 9: 12 / 12