Submission #841442

#	Time	Username	Problem	Language	Result	Execution time	Memory
841442		model_code	Beech Tree (IOI23_beechtree)	C++17	22 / 100	257 ms	89100 KiB

beechtree

// incorrect/solution-keshi-wa.cpp

// In the name of God
#include "beechtree.h"

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

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e5 + 100;

#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

int n, m;
int a[maxn], p[maxn], sz[maxn];
vector<pii> g[maxn];
map<int, int> gsz[maxn];
set<pii> st[maxn];
bool ok[maxn];

void dfs(int v)
{
    sz[v] = 1;
    for (pii u : g[v])
    {
        dfs(u.F);
        sz[v] += sz[u.F];
        if (gsz[v].count(u.S))
            ok[v] = false;
        gsz[v][u.S] = sz[u.F];
    }
    return;
}

bool check(int v, int u)
{
    if (Sz(gsz[v]) > Sz(gsz[u]))
        return 0;
    for (pii i : gsz[v])
    {
        auto it = gsz[u].find(i.F);
        if (it == gsz[u].end() && i.S > it->S)
            return 0;
    }
    return 1;
}

bool add(int x, pii o)
{
    st[x].insert(o);

    auto it = st[x].find(o);

    if (it != st[x].begin())
    {
        auto it2 = it;
        it2--;
        if (!check(it2->S, o.S))
            return 0;
    }

    it++;

    if (it != st[x].end())
    {
        if (!check(o.S, it->S))
            return 0;
    }

    return 1;
}

void solve(int v)
{
    st[v].insert(Mp(sz[v], v));
    for (pii uu : g[v])
    {
        int u = uu.F;
        solve(u);
        ok[v] &= ok[u];
        if (Sz(st[v]) < Sz(st[u]))
            st[v].swap(st[u]);
        for (pii i : st[u])
        {
            ok[v] &= add(v, i);
        }
    }
    return;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{

    /*

    p[i] : parent of node i
    a[i] : the color of the edge between node i and p[i]

    sz[i] : the size of the subtree of node i
    g[i] : vector of <child, color>
    gsz[i] : map of <color, sz of child with that color>
    st[i] : set of <sz, node>

    */

    n = N - 1, m = M;
    for (int i = 1; i <= n; i++)
    {
        p[i] = P[i], a[i] = C[i];
        g[p[i]].pb(Mp(i, a[i]));
    }
    fill(ok, ok + n + 10, 1);
    dfs(0);
    solve(0);

    vector<int> ans(N);
    for (int i = 0; i <= n; i++)
    {
        ans[i] = ok[i];
    }
    return ans;
}

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