Submission #918373

#	Time	Username	Problem	Language	Result	Execution time	Memory
918373		vjudge1	Papričice (COCI20_papricice)	C++17	50 / 110	1062 ms	18076 KiB

papricice

#include "bits/stdc++.h"
using namespace std;
vector< vector<long long> > Lista;
vector< pair<long long, long long> > Orden;
long long Tiempo = 1;
vector<bool> Visitados;
void DFS(long long Nodo){
    Visitados[Nodo] = 1;
    Orden[Nodo].first = Tiempo;
    Tiempo++;
    for(auto E: Lista[Nodo]) if(!Visitados[E]) DFS(E);
    Orden[Nodo].second = Tiempo;
    Tiempo++;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin>>n;
    Lista.assign(n, vector<long long>());
    Visitados.assign(n, 0);
    Orden.assign(n, make_pair(2222222222222222, 2222222222222222));
    for(long long i = 0; i < n - 1; i++){
        long long a, b;
        cin>>a>>b;
        Lista[a - 1].push_back(b - 1);
        Lista[b - 1].push_back(a - 1);
    }
    long long Hoja = 0;
    for(long long i = 0; i < n; i++){
        if(Lista[i].size() == 1){
            DFS(i);
            Hoja = i;
            break;
        }
    }
    long long Respuesta = 2222222222222222;
    for(long long i = 0; i < n - 1; i++){
        if(i == Hoja) continue;
        for(long long j = i + 1; j < n; j++){
            if(j == Hoja) continue;
            long long Tama_o_1 = (Orden[Hoja].second - Orden[Hoja].first + 1) / 2;
            long long Tama_o_2 = (Orden[i].second - Orden[i].first + 1) / 2;
            long long Tama_o_3 = (Orden[j].second - Orden[j].first + 1) / 2;
            if(Orden[i].first <= Orden[j].first and Orden[i].second >= Orden[j].second){
                Tama_o_1 -= Tama_o_2;
                Tama_o_2 -= Tama_o_3;
            } else if(Orden[j].first <= Orden[i].first and Orden[j].second >= Orden[i].second){
                Tama_o_1 -= Tama_o_3;
                Tama_o_3 -= Tama_o_2;
            } else Tama_o_1 -= Tama_o_2 + Tama_o_3;
            Respuesta = min(Respuesta, max(max(Tama_o_1, Tama_o_2), Tama_o_3) - min(min(Tama_o_1, Tama_o_2), Tama_o_3));
        }
    }
    cout<<Respuesta;
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60