제출 #1046482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046482		slivajan	참나무 (IOI23_beechtree)	C++17	0 / 100	2102 ms	54356 KiB

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(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
• 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