Submission #1065677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065677		Zicrus	Beech Tree (IOI23_beechtree)	C++17	17 / 100	96 ms	30292 KiB

beechtree

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

ll n;
vector<int> c;
vector<int> res;
vector<vector<ll>> adj;
vector<pair<ll, ll>> szId;
vector<ll> dep;

ll dfsDep(ll cur) {
    ll d = 0;
    for (auto &e : adj[cur]) {
        d = max(d, dfsDep(e)+1);
    }
    return dep[cur] = d;
}

void dfsSzId(ll cur) {
    szId.push_back({adj[cur].size(), cur});
    for (auto &e : adj[cur]) {
        dfsSzId(e);
    }
}

void solve2(ll root) {
    szId.clear();
    dfsSzId(root);
    sort(szId.begin(), szId.end());

    unordered_set<ll> used;
    if (adj[root].size() != szId.back().first) res[root] = 0;
    for (auto &e : adj[root]) {
        if (used.count(c[e]))
            res[root] = 0;
        used.insert(c[e]);
    }
    for (int i = szId.size()-1; i >= 1; i--) {
        unordered_set<ll> nw;
        for (auto &e : adj[szId[i].second]) {
            if (!used.count(c[e]))
                res[root] = 0;
            if (nw.count(c[e]))
                res[szId[i].second] = res[root] = 0;
            nw.insert(c[e]);
        }
        used = nw;
    }
}

void dfsSol(ll cur) {
    if (dep[cur] <= 2) return solve2(cur);
    res[cur] = 0;
    for (auto &e : adj[cur]) {
        dfsSol(e);
    }
}
 
vector<int> beechtree(int n1, int m, vector<int> p, vector<int> c1) {
    n = n1; c = c1;
    res = vector<int>(n, 1);
    adj = vector<vector<ll>>(n);
    dep = vector<ll>(n);
    for (int i = 1; i < n; i++) {
        adj[p[i]].push_back(i);
    }
    dfsDep(0);
    dfsSol(0);
    return res;
}

#ifdef TEST
#include "grader.cpp"
#endif

Compilation message (stderr)

beechtree.cpp: In function 'void solve2(ll)':
beechtree.cpp:35:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   35 |     if (adj[root].size() != szId.back().first) res[root] = 0;
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 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