Submission #1191553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191553		dvdcoder	Dreaming (IOI13_dreaming)	C++20	47 / 100	42 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];
int auxNode, auxDist;
int anc[MAXN];
int distAnc[MAXN];

void maisLonge(int atual, int pai, int 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, int 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]});
    }
    int maiorDiametro = 0;
    int mr1 = 0, mr2 = 0;

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

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

        maiorDiametro = max(maiorDiametro, diametro);

        if(menorMaiorRaio != INT_MAX) {
            if(menorMaiorRaio > mr2) mr2 = menorMaiorRaio;
            if(mr2 > mr1) swap(mr1, mr2);
        }
    }

    return max(maiorDiametro, mr1 + mr2 + L);
}

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