Submission #1137103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137103		Gabriel	Triumphal arch (POI13_luk)	C++20	0 / 100	526 ms	47752 KiB

luk

#include "bits/stdc++.h"
using namespace std;
vector< vector<long long> > Grafo;
vector<long long> Distancia, Mejores, Precios, Fila;
bool Probar(long long Salario){
    deque<long long> Cola;
    long long n = Grafo.size();
    long long Precio = -0;
    for(long long i = 0; i < n; i++) Precio = max(Precio, Distancia[i]);
    long long i = 0;
    Mejores.assign(n, 2222222222222222);
    for(; Precio > -1; Precio--){
        for(; i < n and Distancia[Fila[i]] == Precio; i++){
            Cola.push_back(Fila[i]);
        }
        for(long long j = 0; j < Cola.size(); j++){
            long long Nodo = Cola[j];
            if(Grafo[Nodo].size() == 1) Mejores[Nodo] = 0;
            else {
                vector<long long> Tomo;
                for(auto E: Grafo[Nodo]){
                    if(Mejores[E] != 2222222222222222){
                        Tomo.push_back(Mejores[E] + Salario);
                    }
                }
                sort(Tomo.begin(), Tomo.end());
                Tomo[0] -= Salario;
                long long Tengo = Precios[Nodo];
                for(long long k = 0; k < Tomo.size(); k++){
                    if(Tomo[k] < 0) Tengo += Tomo[k];
                }
                Mejores[Nodo] = min(0LL, Tengo);
            }
        }
        Cola.clear();
    }
    /*cout<<Salario<<"\n";
    for(auto E: Mejores) cout<<E<<" ";
    cout<<"\n";
    for(auto E: Precios) cout<<E<<" ";
    cout<<"\n";*/
    return Mejores[0] >= 0;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin>>n;
    if(n == 1){
        cout<<0;
        return 0;
    }
    if(n == 2){
        cout<<1;
        return 0;
    }
    Grafo.assign(n, {});
    for(long long i = 0; i < n - 1; i++){
        long long a, b;
        cin>>a>>b;
        a--;
        b--;
        Grafo[a].push_back(b);
        Grafo[b].push_back(a);
    }
    deque<long long> Cola = {0};
    Distancia.assign(n, 2222222222222222);
    Distancia[0] = 0;
    while(!Cola.empty()){
        long long Nodo = Cola[0];
        Cola.pop_front();
        for(auto E: Grafo[Nodo]) if(Distancia[Nodo] + 1 < Distancia[E]){
            Distancia[E] = Distancia[Nodo] + 1;
            Cola.push_back(E);
        }
    }
    long long Izquierda = -0, Derecha = n + 22;
    Precios.assign(n, 0);
    Fila.assign(n, 0);
    set< pair<long long, long long> > Orden;
    for(long long i = 0; i < n; i++){
        Orden.insert(make_pair(Distancia[i], i));
        Precios[i] = -Grafo[i].size() + 1;
        if(i == 0) Precios[i]--;
    }
    long long p = n - 1;
    for(auto E: Orden){
        Fila[p] = E.second;
        p--;
    }
    long long Mejor = Derecha;
    /*for(long long i = 0; i < n; i++) cout<<Precios[i]<<" ";
    cout<<"\n";*/
    while(Izquierda <= Derecha){
        long long Promedio = (Izquierda + Derecha) / 2;
        for(long long i = 0; i < n; i++) Precios[i] += Promedio;
        if(Probar(Promedio)){
            Derecha = Promedio - 1;
            Mejor = Promedio;
        } else Izquierda = Promedio + 1;
        for(long long i = 0; i < n; i++) Precios[i] -= Promedio;
    }
    cout<<Mejor;
    return 0;
}
/*
16
1 3
2 1
4 1
3 5
6 3
2 7
7 8
7 9
7 10
7 11
12 7
13 4
16 13
14 13
13 15
*/
/*
15
1 3
2 1
4 1
13 7
3 5
6 3
2 8
2 9
2 10
2 11
12 2
13 4
14 13
13 15
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10