oj.uz

Submission #1083449

# Submission time Handle Problem Language Result Execution time Memory
1083449 2024-09-03T08:19:02 Z SamueleVid Beech Tree (IOI23_beechtree) C++17
9 / 100
 2000 ms 29384 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 2e5 + 5;
constexpr int MAXM = 500 + 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';
}

void generate_permutation(int u, int i) {
    // cout << "permutazione u : " << u << " i : " << i << '\n';
    if (sol[u]) return;
    if (i == curr.size()) return vediamo(u);
    for (int j = 0; j < curr.size(); j ++) {
        if (v[j]) continue;
        v[j] = 1;
        permutato.push_back(curr[j]);
        generate_permutation(u, i + 1);
        permutato.pop_back();
        v[j] = 0;
    }
}

void check(int u) {
    v.assign(curr.size(), 0);
    permutato.clear();
    // cout << "curr_size di " << u << " e " << curr.size() << '\n';
    permutato.push_back(u);
    generate_permutation(u, 0);
}

void dfs(int u) {
    // cout << "dfs " << u << '\n';
    curr.push_back(u);

    for (auto x : adj[u]) {
        if (x == P[u]) continue;
        dfs(x);
    }
}

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);

    for (int i = 0; i < N; i ++) {
        // cout << "i : " << i << '\n';
        curr.clear();
        fill(colori_usati, colori_usati + MAXM, 0);
        
        for (auto x : adj[i]) {
            if (x == P[i]) continue;
            dfs(x);
        }

        // cout << "fatto dfs: curr ";
        // for (auto x : curr) cout << x << " ";
        // cout << '\n';

        // cout << "curr per " << i << " : ";
        // for (auto x : curr) cout << x << " ";
        // cout << '\n';

        // cout << "ora check" << '\n';

        check(i);
    }

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

Compilation message

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 ++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
beechtree.cpp: In function 'void generate_permutation(int, int)':
beechtree.cpp:59:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if (i == curr.size()) return vediamo(u);
      |         ~~^~~~~~~~~~~~~~
beechtree.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int j = 0; j < curr.size(); j ++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Execution timed out 2074 ms 4956 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5140 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 5136 KB Output is correct
7 Correct 2 ms 5140 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 2 ms 5040 KB Output is correct
10 Correct 2 ms 5136 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 3 ms 5144 KB Output is correct
14 Correct 2 ms 5140 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4952 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4952 KB Output is correct
19 Correct 3 ms 4952 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 4956 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 2 ms 4956 KB Output is correct
24 Correct 2 ms 5100 KB Output is correct
25 Correct 3 ms 4956 KB Output is correct
26 Correct 2 ms 4952 KB Output is correct
27 Correct 2 ms 4956 KB Output is correct
28 Correct 2 ms 4956 KB Output is correct
29 Correct 4 ms 4952 KB Output is correct
30 Correct 2 ms 4956 KB Output is correct
31 Correct 2 ms 4956 KB Output is correct
32 Correct 3 ms 4956 KB Output is correct
33 Correct 2 ms 4956 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5140 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 5136 KB Output is correct
7 Execution timed out 2062 ms 29384 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 4952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5140 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Execution timed out 2062 ms 29384 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Execution timed out 2074 ms 4956 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5140 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 5040 KB Output is correct
6 Correct 2 ms 5136 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 3 ms 5144 KB Output is correct
10 Correct 2 ms 5140 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4952 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4952 KB Output is correct
15 Correct 3 ms 4952 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 5100 KB Output is correct
21 Correct 3 ms 4956 KB Output is correct
22 Correct 2 ms 4952 KB Output is correct
23 Correct 2 ms 4956 KB Output is correct
24 Correct 2 ms 4956 KB Output is correct
25 Execution timed out 2033 ms 5464 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Execution timed out 2074 ms 4956 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5140 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 5040 KB Output is correct
6 Correct 2 ms 5136 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 3 ms 5144 KB Output is correct
10 Correct 2 ms 5140 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4952 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4952 KB Output is correct
15 Correct 3 ms 4952 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 5100 KB Output is correct
21 Correct 3 ms 4956 KB Output is correct
22 Correct 2 ms 4952 KB Output is correct
23 Correct 2 ms 4956 KB Output is correct
24 Correct 2 ms 4956 KB Output is correct
25 Execution timed out 2033 ms 5464 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Execution timed out 2074 ms 4956 KB Time limit exceeded
3 Halted 0 ms 0 KB -