Submission #1136886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136886		Gabriel	Triumphal arch (POI13_luk)	C++20	0 / 100	97 ms	19272 KiB

luk

#include "bits/stdc++.h"
using namespace std;
vector<bool> Visitados;
vector< vector<long long> > Grafo;
bool Probar(long long Nodo, long long Gratis, long long Constructores){
    Visitados[Nodo] = 1;
    bool r = 1;
    long long Necesario = Grafo[Nodo].size() - 1;
    if(Necesario > Gratis) return 0;
    Gratis += Constructores - Necesario;
    for(auto E: Grafo[Nodo]){
        if(!Visitados[E]) r = r or Probar(E, Gratis, Constructores);
    }
    return r;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n, i = 0, d, Mejor;
    cin>>n;
    d = n + 22;
    Mejor = d;
    Grafo.assign(n + 1, {});
    Grafo[0].push_back(n);
    Grafo[n].push_back(0);
    n--;
    while(n--){
        long long a, b;
        cin>>a>>b;
        a--;
        b--;
        Grafo[a].push_back(b);
        Grafo[b].push_back(a);
    }
    n = Grafo.size();
    while(1){
        long long p = (i + d) / 2;
        Visitados.assign(n, 0);
        Visitados.back() = 1;
        if(Probar(0, p, p)){
            d = p - 1;
            Mejor = p;
        } else i = p + 1;
        if(i >= d + 1) break;
    }
    cout<<Mejor;
    return 0;
}

• 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