Submission #1226925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226925		mariaclara	Beech Tree (IOI23_beechtree)	C++20	0 / 100	2094 ms	19468 KiB

beechtree

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back 
#define fr first 
#define sc second 

vi beechtree(int N, int M, vi P, vi C) {
    vi ans(N);
    vector<vi> edges(N);

    for(int i = 1; i <= N-1; i++)
        edges[P[i]].pb(i), C[i]--;

    vi color_qtd(M), vis(N), in_sub(N);

    for(int i = 0; i <= N-1; i++) { // check do i
        vi sub, sub_end;

        queue<int> fila;
        fila.push(i);
        vis[i] = 1;

        while(!fila.empty()) {
            int x = fila.front();
            fila.pop();

            if(x != i and !in_sub[P[x]])
                in_sub[P[x]] = 1, sub.pb(P[x]);
            
            if(edges[x].empty()) sub_end.pb(x);

            for(auto viz : edges[x]) {
                if(!vis[viz]) {
                    fila.push(viz);
                    vis[viz]  = 1;
                }
            }
        }
    
        for(auto it : sub_end) sub.pb(it);

        ans[i] = 1;
        for(int j = 1; j < sz(sub); j++) {
            if(P[sub[j]] != sub[color_qtd[C[sub[j]]]]) ans[i] = 0;
            color_qtd[C[sub[j]]]++;
        }

        for(auto it : sub) 
            vis[it] = in_sub[it] = color_qtd[C[it]] = 0;
    }

    return ans;
}

• 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