Submission #1058676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058676		perekopskad	Beech Tree (IOI23_beechtree)	C++17	31 / 100	44 ms	20076 KiB

beechtree

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define el '\n'
#define ff first
#define ss second
#define pii pair <ll, ll>
#define pb push_back
#define mkp make_pair
#define fr(i, l, r) for(ll i = l; i <= r; i++)
#define debug(x) \
    { cout << #x << " = " << x << el; }

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

const ll N = 2e5 + 10;
const ll M = 1e5 + 10;
const ll K = 400;
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll LOG = 20;
const ll mod = 1000002022;
mt19937 rnd(time(0));

int p[N], c[N], cnt[N], sz[N], h[N];
vector <int> g[N], x, ans;

void dfs1(int v) {
    x.pb(v);
    for(int u : g[v])
        dfs1(u);
}

bool comp(int a, int b) {
    return sz[a] > sz[b];
}

int check(vector <int> &v) {
    int k = 1;
    for(int j = 1; j < v.size(); j++) {
        int par = cnt[c[v[j]]];
        cnt[c[v[j]]]++;
        if(p[v[j]] != v[par]) k = 0;
    }
    for(int j = 0; j < v.size(); j++)
        cnt[c[v[j]]] = 0;

    return k;
}
/*
10 3
-1 0 0 0 1 1 1 2 2 3
0 2 3 1 3 1 2 3 2 1
*/

void dfs2(int v) {
    h[v] = 0;
    sz[v] = 1;
    int mx = 0, good = 1;
    for(int u : g[v]) {
        cnt[c[u]]++;
        chmax(mx, cnt[c[u]]);
    }
    for(int u : g[v])
        cnt[c[u]] = 0;

    for(int u : g[v]) {
        dfs2(u);
        chmax(h[v], h[u] + 1);
        sz[v] += sz[u];
        good &= ans[u];
    }

    if(mx > 1 || h[v] > 2 || !good) return;
    if(h[v] <= 1) {
        ans[v] = 1;
        return;
    }

    sort(g[v].begin(), g[v].end(), comp);
    vector <int> p = {v};
    for(int i : g[v])
        p.pb(i);

    for(int i : g[v])
        for(int i2 : g[i])
            p.pb(i2);

    if(check(p)) ans[v] = 1;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
    fr(i, 0, N - 1) {
        p[i] = P[i];
        c[i] = C[i];
        if(i) g[p[i]].pb(i);
    }
    ans.resize(N);

    bool k = 1;
    fr(i, 0, N - 1)
        k &= (p[i] == i - 1);

    if(k) {
        int cnt = 0;
        for(int i = N - 1; i >= 0; i--) {
            if(i + cnt == N - 1) ans[i] = 1;
            cnt += (C[i] == C[N - 1]);
        }
        return ans;
    }

    if(N <= 8) {
        vector <int> ans(N);
        fr(i, 0, N - 1) {
            x.clear();
            dfs1(i);
            sort(x.begin(), x.end());
            int good = 0;
            do {
                int k = 1;

                if(x[0] != i)
                    continue;

                for(int j = 1; j < x.size(); j++) {
                    int par = cnt[c[x[j]]];
                    cnt[c[x[j]]]++;
                    if(p[x[j]] != x[par]) k = 0;
                }
                for(int j = 0; j < x.size(); j++)
                    cnt[c[x[j]]] = 0;
                if(k) {
                    good = 1;
                    break;
                }
            }while(next_permutation(x.begin(), x.end()));
            ans[i] = good;
        }
        return ans;
    }

    dfs2(0);
    return ans;
}

/*
int main()
{
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));
    std::vector<int> P(N);
    for (int i = 0; i < N; ++i)
        assert(1 == scanf("%d", &P[i]));
    std::vector<int> C(N);
    for (int i = 0; i < N; ++i)
        assert(1 == scanf("%d", &C[i]));

    fclose(stdin);

    std::vector<int> res = beechtree(N, M, P, C);

    int n = res.size();
    for (int i = 0; i < n; ++i)
    {
        if (i > 0)
            printf(" ");
        printf("%d", res[i]);
    }
    printf("\n");
    fclose(stdout);

    return 0;
}
*/

Compilation message (stderr)

beechtree.cpp: In function 'int check(std::vector<int>&)':
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 |     for(int j = 1; j < v.size(); j++) {
      |                    ~~^~~~~~~~~~
beechtree.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j = 0; j < v.size(); j++)
      |                    ~~^~~~~~~~~~
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:136:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |                 for(int j = 1; j < x.size(); j++) {
      |                                ~~^~~~~~~~~~
beechtree.cpp:141:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |                 for(int j = 0; j < x.size(); j++)
      |                                ~~^~~~~~~~~~

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