Submission #1058657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058657		Ignut	Beech Tree (IOI23_beechtree)	C++17	9 / 100	74 ms	20424 KiB

beechtree

/* Ignut
started: 14.08.2024
now: 14.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 123;
int n;

vector<int> tree[MAXN];
vector<int> p;
vector<int> c;

vector<int> res;

int cnt[MAXN] = {};

int depth[MAXN];

bool Check(vector<int> &lst, int root) {
    sort(lst.begin(), lst.end());
    do {
        bool ok = true;
        for (int i = 0; i < lst.size(); i ++) {
            int v = lst[i];
            

            int par = cnt[c[v]];
            int vert = (par == 0 ? root : lst[par - 1]);
            if (p[v] != vert) {
                ok = false; break;
            }
            cnt[c[v]] ++;
        }
        for (int v : lst) cnt[c[v]] = 0;
        if (ok) return true;
    } while (next_permutation(lst.begin(), lst.end()));
    return false;
}

vector<int> dfs(int v) {
    vector<int> lst = {};
    for (int to : tree[v])
        if (to != p[v])
            for (int u : dfs(to))
                lst.push_back(u);
    res[v] |= Check(lst, v);
    lst.push_back(v);
    return lst;
}


void dfs0(int v, int d) {
    depth[v] = d;
    for (int to : tree[v])
        if (to != p[v])
            dfs0(to, d + 1);
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    n = N; p = P; c = C;
    res.assign(N, 0);
    if (N <= 8) {
        // cout << "brute\n";
        for (int i = 1; i < N; i ++) {
            tree[i].push_back(P[i]);
            tree[P[i]].push_back(i);
        }
        dfs0(0, 0);
        dfs(0);
        return res;
    }

    vector<int> v1, v2;
    for (int i = 1; i < N; i ++) {
        if (p[i] == 0) v1.push_back(i);
        else v2.push_back(i);
        res[i] = 1;
    }
    set<int> st;
    for (int v : v1) {
        st.insert(c[v]);
    }
    if (st.size() != v1.size())
        return res;
    set<int> st2;
    for (int v : v2) st2.insert(c[v]);
    if (st2.size() > 1) return res;
    if (st2.empty()) {
        res[0] = 1; return res;
    }
    int val = *st2.begin();
    int prv = st.size();
    st.insert(val);
    if (st.size() > prv) return res;
    res[0] = 1;
    return res;
}

Compilation message (stderr)

beechtree.cpp: In function 'bool Check(std::vector<int>&, int)':
beechtree.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int i = 0; i < lst.size(); i ++) {
      |                         ~~^~~~~~~~~~~~
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:121:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |     if (st.size() > prv) return res;
      |         ~~~~~~~~~~^~~~~

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