Submission #1083473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083473		SamueleVid	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2090 ms	1056676 KiB

beechtree

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

constexpr int MAXN = 2e5 + 5;
constexpr int MAXM = 2e5 + 5;
vector<int> P, C;
vector<int> curr;
vector<int> permutato;
vector<bool> v;
vector<int> adj[MAXN];
int colori_usati[MAXM];
bool sol[MAXN];

void vediamo(int u) {
    // cout << "vediamo " << u << '\n';
    // colori_usati[C[u]] ++;

    vector<int> to_remove;

    // cout << "colori_usati : ";
    // for (int i = 0; i < 4; i ++) cout << colori_usati[i] << " ";
    // cout << '\n';

    // cout << "permutazione da verificare per " << u << " : ";
    // for (auto x : permutato) cout << x << " ";
    // cout << '\n';



    for (int i = 1; i < permutato.size(); i ++) {
        int f_i = colori_usati[C[permutato[i]]];
        // cout << "permutato[i], f_i : " << permutato[i] << " " << f_i << '\n';
        if (P[permutato[i]] != permutato[f_i]) {
            for (auto x : to_remove) colori_usati[x] --;
            return;
        }
        to_remove.push_back(C[permutato[i]]);
        colori_usati[C[permutato[i]]] ++;
    }
    
    // cout << "permutazione valida per " << u << " : ";
    // for (auto x : permutato) cout << x << " ";
    // cout << '\n';


    // cout << "sol[u] = 1 !!" << '\n';
    
    for (auto x : to_remove) colori_usati[x] --;

    sol[u] = 1;

    // for (int i = 0; i < 4; i ++) cout << sol[i] << " ";
    // cout << '\n';
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    ::P = P;
    ::C = C;
    for (int i = 1; i < N; i ++) {
        adj[P[i]].push_back(i);
        adj[i].push_back(P[i]);
    }

    fill(sol, sol + N, 0);
    fill(colori_usati, colori_usati + MAXM, 0);

    for (int i = N - 1; i >= 0; i ++) {
        permutato.push_back(i);
        vediamo(i);
    }

    vector<int> res(N);
    for (int i = 0; i < N; i ++) res[i] = sol[i];
    return res;
}

Compilation message (stderr)

beechtree.cpp: In function 'void vediamo(int)':
beechtree.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 1; i < permutato.size(); 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