Submission #854878

#	Time	Username	Problem	Language	Result	Execution time	Memory
854878		piOOE	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2041 ms	276720 KiB

beechtree

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

using namespace std;

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
    vector<int> sh(C);
    sort(sh.begin(), sh.end());
    sh.resize(unique(sh.begin(), sh.end()) - sh.begin());
    M = size(sh);
    for (int i = 0; i < N; ++i) {
        C[i] = lower_bound(sh.begin(), sh.end(), C[i]) - sh.begin();
    }

    vector<int> ans(N, 1), isOk(N, 1), siz(N, 1);
    vector<vector<int>> adj(N), sub(N);

    for (int i = N - 1; i > 0; --i) {
        adj[P[i]].push_back(i);
    }

    for (int v = N - 1; v >= 0; --v) {
        static vector<int> cnt(M);
        for (int to : adj[v]) {
            cnt[C[to]] = 0;
            isOk[v] &= isOk[to];
        }
        for (int to : adj[v]) {
            siz[v] += siz[to];
            isOk[v] &= ++cnt[C[to]] == 1;
        }
        ans[v] = isOk[v];
        if (!isOk[v]) {
            continue;
        }
        for (int to : adj[v]) {
            sub[v].insert(sub[v].end(), sub[to].begin(), sub[to].end());
            sub[to].clear();
        }
        static vector<int> last(N, -1);
        last[v] = -1;
        for (int x : sub[v]) {
            last[x] = -1;
            ++cnt[C[x]];
        }
        vector<int> ord = sub[v];
        sort(ord.begin(), ord.end(), [&](int x, int y) { return pair{cnt[C[x]], C[x]} > pair{cnt[C[y]], C[y]}; });
        for (int i = 0, j = 0, k = -1; i < size(ord); i = j) {
            int sum = 0;
            while (j < size(ord) && C[ord[j]] == C[ord[i]]) {
                int x = ord[j++];
                while (x != v) {
                    x = P[x];
                    if (last[x] == i) {
                        break;
                    } else if (last[x] != k) {
                        ans[v] = 0;
                        break;
                    }
                    sum += 1;
                    last[x] = i;
                }
                if (!ans[v]) {
                    break;
                }
            }
            if (!ans[v] || sum != j - i) {
                ans[v] = 0;
                break;
            }
            k = i;
        }
        if (!ans[v]) {
            sub[v].push_back(v);
            continue;
        }
        vector<int> q;
        set<pair<int, int>> st;
        st.emplace(siz[v], v);
        for (int i = 0; !st.empty() && ans[v]; ++i) {
            q.push_back(st.rbegin()->second);
            st.erase(--st.end());
            int x = q[i];
            if (i > 0) {
                int c = 0;
                for (int j = 1; j < i; ++j) {
                    c += C[q[j]] == C[x];
                }
                if (P[x] != q[c]) {
                    ans[v] = 0;
                    break;
                }
            }
            sort(adj[x].begin(), adj[x].end(), [&](int a, int b) { return siz[a] > siz[b]; });
            for (int to : adj[x]) {
                st.emplace(siz[to], to);
            }
        }
        sub[v].push_back(v);
    }

    return ans;
}

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:48:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i = 0, j = 0, k = -1; i < size(ord); i = j) {
      |                                        ~~^~~~~~~~~~~
beechtree.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             while (j < size(ord) && C[ord[j]] == C[ord[i]]) {
      |                    ~~^~~~~~~~~~~

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