답안 #1046498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046498	2024-08-06T15:52:04 Z	slivajan	참나무 (IOI23_beechtree)	C++17	0 / 100	2000 ms	54424 KB

beechtree

#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(porad[j]);
                    if (deti[porad[j]].stats[dostupne[i]][e] == ZERO) bads.push_back(porad[j]);
                }
                un neutral = porad[pos];

                REP(j, *L, *L + (un)goods.size()) porad[j] = goods[j - (*L)];
                porad[*L + (un)goods.size()] = neutral;
                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

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
4	Halted	0 KB	-

Subtask #1
0.0 / 9.0

#	결과	실행 시간	메모리	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	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	344 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

#	결과	실행 시간	메모리	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	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	66 ms	54424 KB	Output is correct
8	Correct	73 ms	54424 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	20 ms	1092 KB	Output is correct
14	Correct	11 ms	1088 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	2102 ms	54232 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #3
0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 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	1 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

#	결과	실행 시간	메모리	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	1 ms	344 KB	Output is correct
5	Correct	66 ms	54424 KB	Output is correct
6	Correct	73 ms	54424 KB	Output is correct
7	Incorrect	0 ms	348 KB	2nd lines differ - on the 52nd token, expected: '1', found: '0'
8	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 14.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
4	Halted	0 KB	-

Subtask #6
0.0 / 14.0

#	결과	실행 시간	메모리	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	1 ms	344 KB	Output is correct
5	Correct	0 ms	344 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

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
4	Halted	0 KB	-

Subtask #8
0.0 / 17.0

#	결과	실행 시간	메모리	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	1 ms	344 KB	Output is correct
5	Correct	0 ms	344 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

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
4	Halted	0 KB	-

답안 #1046498

Compilation message