제출 #1191558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191558		dvdcoder	Dreaming (IOI13_dreaming)	C++20	100 / 100	43 ms	14408 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

#define MAXN 100002
#define pb push_back
typedef long long ll;
using namespace std;

vector <pair<int, int>> viz[MAXN];
int visitado[MAXN];
ll auxNode, auxDist;
int anc[MAXN];
int distAnc[MAXN];

void maisLonge(int atual, int pai, ll dist) {
    visitado[atual] = 1;
    anc[atual] = -1;
    distAnc[atual] = 0;
    if(dist > auxDist) auxDist = dist, auxNode = atual;
    for(auto [p, d]:viz[atual]) {
        if(p == pai) continue;
        maisLonge(p, atual, dist+d);
    }
}

void maisLongeAtualizaPai(int atual, int pai, ll dist) {
    if(dist > auxDist) auxDist = dist, auxNode = atual;
    for(auto [p, d]:viz[atual]) {
        if(p == pai) continue;
        anc[p] = atual;
        distAnc[p] = d;
        maisLongeAtualizaPai(p, atual, dist+d);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < MAXN; i++) {
        viz[i].clear();
        visitado[i] = 0;
    }

    for(int i = 0; i < M; i++) {
        viz[A[i]].pb({B[i], T[i]});
        viz[B[i]].pb({A[i], T[i]});
    }
    ll maiorDiametro = 0;
    ll mr1 = 0, mr2 = 0, mr3 = 0;

    for(int i = 0; i < N; i++) {
        if(visitado[i]) continue;
        auxNode = i, auxDist = 0;
        maisLonge(i, i, 0);
        int ponta1 = auxNode;
        auxNode = i, auxDist = 0;
        anc[ponta1] = ponta1; distAnc[ponta1] = 0;
        maisLongeAtualizaPai(ponta1, ponta1, 0);
        
        int ponta2 = auxNode;
        ll diametro = auxDist;
        ll raioAtual = 0;
        ll menorMaiorRaio = LLONG_MAX;

        while(ponta1 != ponta2) {
            raioAtual += distAnc[ponta2];
            menorMaiorRaio = min(max(diametro - raioAtual, raioAtual), menorMaiorRaio);
            ponta2 = anc[ponta2];
        }

        maiorDiametro = max(maiorDiametro, diametro);

        if(menorMaiorRaio != LLONG_MAX) {
            if(menorMaiorRaio > mr3) mr3 = menorMaiorRaio;
            if(mr3 > mr2) swap(mr3, mr2);
            if(mr2 > mr1) swap(mr1, mr2);
        }
    }
    // if(mr2 == -1) return maiorDiametro;
    // if(mr3 == -1) return max({maiorDiametro, mr1 + mr2 + L});
    if(M == N-1) return maiorDiametro;
    if(M == N-2) return max({maiorDiametro, mr1 + mr2 + L}); 
    return max({maiorDiametro, mr1 + mr2 + L, mr2 + mr3 + 2*L});
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23