Submission #841419

#	Time	Username	Problem	Language	Result	Execution time	Memory
841419		model_code	Beech Tree (IOI23_beechtree)	C++17	100 / 100	369 ms	39992 KiB

beechtree

// correct/sol_na_full-2.cpp

#include "beechtree.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <functional>
#include <queue>

#define xx first
#define yy second

std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<int> sz;
std::vector<int> par;
std::vector<int> par_c;
std::vector<int> ans;

void dfs(int x)
{
    sz[x] = 1;
    for (auto i : adj[x])
    {
        dfs(i.xx);
        par[i.xx] = x;
        par_c[i.xx] = i.yy;
        sz[x] += sz[i.xx];
    }
}

std::vector<int> ccnt, where, ord, edgs;
std::priority_queue<std::array<int, 3>> pq;

bool check(int x)
{
    bool ok = true;
    ord.clear();
    edgs.clear();
    pq.push({sz[x], -ord.size(), x});
    while (!pq.empty())
    {
        auto tp = pq.top();
        pq.pop();
        where[tp[2]] = ord.size();
        ord.push_back(tp[2]);
        if (tp[2] != x)
            edgs.push_back(ccnt[par_c[tp[2]]]++);
        for (auto i : adj[tp[2]])
        {
            pq.push({sz[i.xx], -ord.size(), i.xx});
        }
    }

    for (int i = 1; i < ord.size(); ++i)
    {
        ccnt[par_c[ord[i]]] = 0;
    }

    for (int i = 1; i < (int)ord.size(); ++i)
    {
        ok &= edgs[i - 1] == where[par[ord[i]]];
    }

    return ok;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    adj.resize(N);
    sz.resize(N);
    par.assign(N, -1);
    par_c.assign(N, 0);
    ans.assign(N, -1);
    ccnt.assign(M + 1, 0);
    where.assign(N, -1);
    for (int i = 1; i < N; ++i)
    {
        adj[P[i]].push_back({i, C[i]});
    }

    dfs(0);

    srand(time(0));

    std::priority_queue<std::pair<int, int>> c;
    std::vector<int> rnd_val(N);
    for (int i = 0; i < N; ++i)
    {
        rnd_val[i] = rand();
        c.push({rnd_val[i], i});
    }

    std::function<void(int)> filldfs;
    filldfs = [&](int x)
    {
        if (rnd_val[x] == -1)
            return;
        ans[x] = 1;
        rnd_val[x] = -1;
        for (auto i : adj[x])
        {
            filldfs(i.xx);
        }
    };

    auto changepars = [&](int x)
    {
        while (x != -1)
        {
            if (rnd_val[x] == -1)
                return;
            ans[x] = 0;
            rnd_val[x] = -1;
            x = par[x];
        }
    };

    while (!c.empty())
    {
        auto x = c.top();
        c.pop();
        if (x.xx != rnd_val[x.yy])
            continue;
        if (check(x.yy))
        {
            filldfs(x.yy);
        }
        else
        {
            changepars(x.yy);
        }
    }

    return ans;
}

Compilation message (stderr)

beechtree.cpp: In function 'bool check(int)':
beechtree.cpp:40:21: warning: narrowing conversion of '- ord.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   40 |     pq.push({sz[x], -ord.size(), x});
      |                     ^~~~~~~~~~~
beechtree.cpp:51:32: warning: narrowing conversion of '- ord.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   51 |             pq.push({sz[i.xx], -ord.size(), i.xx});
      |                                ^~~~~~~~~~~
beechtree.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 1; i < ord.size(); ++i)
      |                     ~~^~~~~~~~~~~~

• 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