oj.uz

Submission #918373

# Submission time Handle Problem Language Result Execution time Memory
918373 2024-01-29T18:19:23 Z vjudge1 Papričice (COCI20_papricice) C++17
50 / 110
 1000 ms 18076 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 11 ms 604 KB Output is correct
7 Correct 11 ms 604 KB Output is correct
8 Correct 11 ms 600 KB Output is correct
9 Correct 11 ms 856 KB Output is correct
10 Correct 14 ms 604 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 11 ms 604 KB Output is correct
7 Correct 11 ms 604 KB Output is correct
8 Correct 11 ms 600 KB Output is correct
9 Correct 11 ms 856 KB Output is correct
10 Correct 14 ms 604 KB Output is correct
11 Execution timed out 1062 ms 18076 KB Time limit exceeded
12 Halted 0 ms 0 KB -