oj.uz

Submission #1083481

# Submission time Handle Problem Language Result Execution time Memory
1083481 2024-09-03T09:31:42 Z SamueleVid Beech Tree (IOI23_beechtree) C++17
14 / 100
 58 ms 13208 KB 
#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';
}

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> lentissimo(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 = 0; i < N; i ++) {
        // cout << "i : " << i << '\n';
        curr.clear();
        
        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;
}

vector<int> path(int N, int M, vector<int> P, vector<int> C) {
    fill(sol, sol + N, 0);

    vector<int> res(N);

    int last_used = C[N - 1];
    int stronzo = 1e9;
    bool funzia = 1;
    for (int i = N - 1; i >= 0; i --) {

        res[i] = funzia;

        if (last_used != C[i]) {
            funzia = 0;
        }
    }

    return res;
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
    if (N <= 8) return lentissimo(N, M, P, C);
    return path(N, M, P, C);
}

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 ++) {
      |                     ~~^~~~~~~~~~~~~
beechtree.cpp: In function 'std::vector<int> path(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:132:9: warning: unused variable 'stronzo' [-Wunused-variable]
  132 |     int stronzo = 1e9;
      |         ^~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Incorrect 2 ms 4956 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 3 ms 5888 KB Output is correct
4 Correct 3 ms 5908 KB Output is correct
5 Correct 3 ms 5724 KB Output is correct
6 Correct 3 ms 5724 KB Output is correct
7 Correct 3 ms 5724 KB Output is correct
8 Correct 3 ms 5724 KB Output is correct
9 Correct 3 ms 5720 KB Output is correct
10 Correct 3 ms 5724 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 4 ms 5724 KB Output is correct
13 Correct 3 ms 5724 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 4 ms 5908 KB Output is correct
16 Correct 3 ms 5912 KB Output is correct
17 Correct 3 ms 5720 KB Output is correct
18 Correct 3 ms 5724 KB Output is correct
19 Correct 3 ms 5724 KB Output is correct
20 Correct 3 ms 5724 KB Output is correct
21 Correct 3 ms 5724 KB Output is correct
22 Correct 3 ms 5724 KB Output is correct
23 Correct 3 ms 5748 KB Output is correct
24 Correct 2 ms 5720 KB Output is correct
25 Correct 3 ms 5724 KB Output is correct
26 Correct 2 ms 5724 KB Output is correct
27 Correct 3 ms 5724 KB Output is correct
28 Correct 3 ms 5724 KB Output is correct
29 Correct 2 ms 5720 KB Output is correct
30 Correct 2 ms 5724 KB Output is correct
31 Correct 3 ms 5724 KB Output is correct
32 Correct 3 ms 5980 KB Output is correct
33 Correct 3 ms 5724 KB Output is correct
34 Correct 2 ms 5724 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 3 ms 5888 KB Output is correct
4 Correct 3 ms 5908 KB Output is correct
5 Correct 3 ms 5724 KB Output is correct
6 Correct 3 ms 5724 KB Output is correct
7 Correct 44 ms 12880 KB Output is correct
8 Correct 58 ms 12996 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 3 ms 5208 KB Output is correct
16 Correct 3 ms 5148 KB Output is correct
17 Correct 41 ms 12876 KB Output is correct
18 Correct 45 ms 13208 KB Output is correct
19 Correct 44 ms 13136 KB Output is correct
20 Correct 53 ms 13140 KB Output is correct

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4956 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5724 KB Output is correct
5 Correct 44 ms 12880 KB Output is correct
6 Correct 58 ms 12996 KB Output is correct
7 Incorrect 2 ms 4956 KB 2nd lines differ - on the 3rd token, expected: '1', found: '0'
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Incorrect 2 ms 4956 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5724 KB Output is correct
5 Correct 3 ms 5720 KB Output is correct
6 Correct 3 ms 5724 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 4 ms 5724 KB Output is correct
9 Correct 3 ms 5724 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 4 ms 5908 KB Output is correct
12 Correct 3 ms 5912 KB Output is correct
13 Correct 3 ms 5720 KB Output is correct
14 Correct 3 ms 5724 KB Output is correct
15 Correct 3 ms 5724 KB Output is correct
16 Correct 3 ms 5724 KB Output is correct
17 Correct 3 ms 5724 KB Output is correct
18 Correct 3 ms 5724 KB Output is correct
19 Correct 3 ms 5748 KB Output is correct
20 Correct 2 ms 5720 KB Output is correct
21 Correct 3 ms 5724 KB Output is correct
22 Correct 2 ms 5724 KB Output is correct
23 Correct 3 ms 5724 KB Output is correct
24 Correct 3 ms 5724 KB Output is correct
25 Correct 3 ms 5208 KB Output is correct
26 Correct 3 ms 4952 KB Output is correct
27 Correct 3 ms 5148 KB Output is correct
28 Correct 2 ms 4956 KB Output is correct
29 Correct 3 ms 4956 KB Output is correct
30 Incorrect 3 ms 4952 KB 2nd lines differ - on the 6th token, expected: '1', found: '0'
31 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Incorrect 2 ms 4956 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5724 KB Output is correct
5 Correct 3 ms 5720 KB Output is correct
6 Correct 3 ms 5724 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 4 ms 5724 KB Output is correct
9 Correct 3 ms 5724 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 4 ms 5908 KB Output is correct
12 Correct 3 ms 5912 KB Output is correct
13 Correct 3 ms 5720 KB Output is correct
14 Correct 3 ms 5724 KB Output is correct
15 Correct 3 ms 5724 KB Output is correct
16 Correct 3 ms 5724 KB Output is correct
17 Correct 3 ms 5724 KB Output is correct
18 Correct 3 ms 5724 KB Output is correct
19 Correct 3 ms 5748 KB Output is correct
20 Correct 2 ms 5720 KB Output is correct
21 Correct 3 ms 5724 KB Output is correct
22 Correct 2 ms 5724 KB Output is correct
23 Correct 3 ms 5724 KB Output is correct
24 Correct 3 ms 5724 KB Output is correct
25 Correct 3 ms 5208 KB Output is correct
26 Correct 3 ms 4952 KB Output is correct
27 Correct 3 ms 5148 KB Output is correct
28 Correct 2 ms 4956 KB Output is correct
29 Correct 3 ms 4956 KB Output is correct
30 Incorrect 3 ms 4952 KB 2nd lines differ - on the 6th token, expected: '1', found: '0'
31 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Incorrect 2 ms 4956 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -