oj.uz

Submission #915258

# Submission time Handle Problem Language Result Execution time Memory
915258 2024-01-23T15:07:42 Z vjudge1 Papričice (COCI20_papricice) C++17
15 / 110
 1000 ms 440 KB 
#include "bits/stdc++.h"
using namespace std;
vector<long long> Representantes;
vector<long long> Tama_os;
void Iniciar(long long n){
    for(long long i = 0; i < n; i++){
        Representantes[i] = i;
        Tama_os[i] = 1;
    }
}
long long Buscar(long long a){
    if(Representantes[a] == a) return a;
    else return Representantes[a] = Buscar(Representantes[a]);
}
void Unir(long long A, long long B){
    long long a = Buscar(A);
    long long b = Buscar(B);
    if(Tama_os[a] > Tama_os[b]){
        Tama_os[a] += Tama_os[b];
        Representantes[b] = a;
    } else {
        Tama_os[b] += Tama_os[a];
        Representantes[a] = b;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin>>n;
    Representantes.assign(n, 1);
    Tama_os.assign(n, 1);
    Iniciar(n);
    vector< pair<long long, long long> > Aristas(n - 1);
    for(long long i = 0; i < n - 1; i++) cin>>Aristas[i].first>>Aristas[i].second;
    long long Respuesta = 2222222222222222;
    for(long long i = 0; i < n - 2; i++){
        for(long long j = i + 1; j < n - 1; j++){
            //cout<<i<<" "<<j<<"\n";
            Iniciar(n);
            for(long long k = 0; k < n - 1; k++) if(k != i and k != j) Unir(Aristas[k].first - 1, Aristas[k].second - 1);
            long long Mayor = -2;
            long long Menor = 2222222222222222;
            for(long long k = 0; k < n; k++){
                Mayor = max(Tama_os[Buscar(k)], Mayor);
                Menor = min(Tama_os[Buscar(k)], Menor);
            }
            Respuesta = min(Respuesta, Mayor - Menor);
        }
    }
    cout<<Respuesta;
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 344 KB Output is correct
2 Correct 43 ms 440 KB Output is correct
3 Correct 45 ms 344 KB Output is correct
4 Correct 47 ms 344 KB Output is correct
5 Correct 44 ms 348 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 344 KB Output is correct
2 Correct 43 ms 440 KB Output is correct
3 Correct 45 ms 344 KB Output is correct
4 Correct 47 ms 344 KB Output is correct
5 Correct 44 ms 348 KB Output is correct
6 Execution timed out 1056 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 344 KB Output is correct
2 Correct 43 ms 440 KB Output is correct
3 Correct 45 ms 344 KB Output is correct
4 Correct 47 ms 344 KB Output is correct
5 Correct 44 ms 348 KB Output is correct
6 Execution timed out 1056 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -