제출 #1191558

#제출 시각아이디문제언어결과실행 시간메모리
1191558dvdcoder꿈 (IOI13_dreaming)C++20
100 / 100
43 ms14408 KiB
#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}); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...