Submission #845866

#	Time	Username	Problem	Language	Result	Execution time	Memory
845866		sebinkim	Beech Tree (IOI23_beechtree)	C++17	58 / 100	2049 ms	56144 KiB

beechtree

#include <bits/stdc++.h>
#include "beechtree.h"

using namespace std;
using piii = tuple<int, int, int>;

vector<int> T[202020];
vector<int> P, C;
int S[202020], K[202020];
int n, m;

void dfs(int u, vector<int> &A) {
    S[u] = 1;
    for (int &v: T[u]) {
        dfs(v, A);
        S[u] += S[v];
    }

    priority_queue<piii> Q;
    vector<int> V;

    fill(K, K + m + 1, 0);
    Q.emplace(S[u], 0, u);

    for (; !Q.empty(); ) {
        auto [_, __, v] = Q.top();
        Q.pop();

        if (v != u) {
            if (K[C[v]] >= V.size() || V[K[C[v]]] != P[v]) return;
            K[C[v]]++;
        }
        V.push_back(v);

        for (int &w: T[v]) {
            Q.emplace(S[w], -V.size(), w);
        }
    }

    A[u] = 1;
}

vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) {
    ::C = C; ::P = P; ::n = n; ::m = m;

    int i;

    for (i = 1; i < n; i++) {
        T[P[i]].push_back(i);
    }

    vector<int> A(n);

    dfs(0, A);

    return A;
}

Compilation message (stderr)

beechtree.cpp: In function 'void dfs(int, std::vector<int>&)':
beechtree.cpp:30:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             if (K[C[v]] >= V.size() || V[K[C[v]]] != P[v]) return;
      |                 ~~~~~~~~^~~~~~~~~~~

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