제출 #1218442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218442		vanea	참나무 (IOI23_beechtree)	C++20	100 / 100	518 ms	124512 KiB

beechtree

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

const int mxN = 2e5+10;

int sz[mxN];
bool pos[mxN];
map<int, vector<int>> adj[mxN];
set<pair<int, int>> vals[mxN];

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

bool add(set<pair<int, int>> &st, pair<int, int> elem) {
    bool result = true;
    auto [it, it2] = st.insert(elem);
    if(it != st.begin()) {
        result &= check(prev(it)->second, it->second);
    }
    if(next(it) != st.end()) {
        result &= check(it->second, next(it)->second);
    }
    return result;
}

int dfs(int node) {
    sz[node] = 1;
    pos[node] = true;
    for(auto [color, v] : adj[node]) {
        pos[node] &= (v.size() == 1);
        for(auto it : v) {
            int nxt_sz = dfs(it);
            if(nxt_sz == -1) pos[node] = false;
            if(pos[node]) sz[node] += nxt_sz;
            if(pos[node]) {
                if(vals[it].size() > vals[node].size()) swap(vals[it], vals[node]);
                for(auto it1 : vals[it]) {
                    pos[node] &= add(vals[node], it1);
                }
            }
        }
    }
    pos[node] &= add(vals[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(adj[p].count(c) == 0) {
            adj[p][c] = vector<int>();
        }
        adj[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