oj.uz

Submission #1046495

# Submission time Handle Problem Language Result Execution time Memory
1046495 2024-08-06T15:46:48 Z slivajan Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 54352 KB 
#include "beechtree.h"

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

typedef int un;
typedef vector<un> vuc;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

#define ZERO 0
#define END 1
#define CONT 2


vec<vuc> strom;
vuc _C;

struct krasny {

    bool opravdu;
    un vrchol;

    map<un, vuc> stats;
};


krasny sluc(vec<krasny> deti, un V){

    FEAC(d, deti){
        if (not d.opravdu) return {false, V, {}};
    }

    set<un> duha;
    map<un, vuc> retStats;
    vuc dostupne;
    FEAC(d, strom[V]){
        if (duha.count(_C[d])) return {false, V, {}};
        duha.insert(_C[d]);
        retStats[_C[d]] = {CONT};
        dostupne.push_back(_C[d]);
    }

    FEAC(d, deti) {
        FEAC(b, d.stats) if (not duha.count(b.first)) return {false, V, {}};
    }

    un max_size = 0;
    FEAC(d, deti) {
        FEAC(b, d.stats){
            max_size = max(max_size, (un)b.second.size());
        }
    }

    FEAC(d, deti) {
        FEAC(b, dostupne){
            if (d.stats.find(b) == d.stats.end()){
                d.stats[b] = {};
            }
            while((un)d.stats[b].size() != max_size) d.stats[b].push_back(ZERO);
        }
    }

    vuc porad(deti.size());
    iota(ALL(porad), 0);

    vuc pevne = {0, (un)deti.size()};

    vec<bool> isDead(dostupne.size(), false);

    REP(e, 0, max_size){
        REP(i, 0, dostupne.size()){
            if (isDead[i]) {
                REP(j, 0, deti.size()){
                    if (deti[porad[j]].stats[dostupne[i]][e] != ZERO){
                        return {false, V, {}};
                    }
                }
                continue;
            }
            
            un pos = -1;
            bool is_end = false;
            REP(j, 0, deti.size()){
                if (deti[porad[j]].stats[dostupne[i]][e] == END){
                    isDead[i] = true;
                    if (pos != -1) return {false, V, {}};
                    pos = j;
                    is_end = true;
                }
            }
            if (pos == -1){
               REP(j, 0, deti.size()){
                    if (deti[porad[j]].stats[dostupne[i]][e] == ZERO){
                        isDead[i] = true;
                        pos = j;
                        break;
                    }
                } 
            }
            if (pos != -1){
                auto L = upper_bound(ALL(pevne), pos);
                L--;
                auto R = upper_bound(ALL(pevne), pos);

                REP(j, 0, *L){
                    if (deti[porad[j]].stats[dostupne[i]][e] != CONT) return {false, V, {}};
                }
                REP(j, *R, deti.size()){
                    if (deti[porad[j]].stats[dostupne[i]][e] != ZERO) return {false, V, {}};
                }

                vuc goods;
                vuc bads;
                REP(j, *L, *R){
                    if (j == pos) continue;
                    if (deti[porad[j]].stats[dostupne[i]][e] == CONT) goods.push_back(j);
                    if (deti[porad[j]].stats[dostupne[i]][e] == ZERO) bads.push_back(j);
                }

                REP(j, *L, *L + (un)goods.size()) porad[j] = goods[j - (*L)];
                porad[*L + (un)goods.size()] = pos;
                REP(j, 0, bads.size()) porad[((un)goods.size() +1) + j] = bads[j];

                pevne.push_back(pos+1);
                if (is_end) pevne.push_back(pos);
                sort(ALL(pevne));

                bool is_blank = true;
                REP(j, 0, deti.size()){
                    if (deti[porad[j]].stats[dostupne[i]][e] != ZERO){
                        is_blank = false;
                    }
                }

                if (is_blank){
                    retStats[dostupne[i]].push_back(ZERO);
                }
                else{
                   retStats[dostupne[i]].push_back(END); 
                }
                continue;
            }
            else{
                retStats[dostupne[i]].push_back(CONT);
            }


        }
    }

    return {true, V, retStats};
}

vec<int> dokaz;

krasny rekurze(un V){
    vec<krasny> lol;

    FEAC(d, strom[V]){
        lol.push_back(rekurze(d));
    }

    krasny ret = sluc(lol, V);
    dokaz[V] = ret.opravdu;

    return ret;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    strom = vec<vuc>(N);
    _C = C;

    REP(i, 1, N){
        strom[P[i]].push_back(i);
    }

    dokaz = vec<int>(N);
    rekurze(0);

    return dokaz;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
11 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 67 ms 54240 KB Output is correct
8 Correct 66 ms 54352 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 21 ms 1088 KB Output is correct
14 Correct 11 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Execution timed out 2101 ms 54236 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 67 ms 54240 KB Output is correct
6 Correct 66 ms 54352 KB Output is correct
7 Incorrect 1 ms 344 KB 2nd lines differ - on the 52nd 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

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