Submission #915258

#	Time	Username	Problem	Language	Result	Execution time	Memory
915258		vjudge1	Papričice (COCI20_papricice)	C++17	15 / 110	1056 ms	440 KiB

papricice

#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 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60