제출 #1309930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309930		lativ	꿈 (IOI13_dreaming)	C++20	0 / 100	32 ms	14872 KiB

dreaming

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

using namespace std;


const int maxn = 1e5+5;

typedef struct Trail {

    int node;
    int time;
    int diam;

} trail;
vector<trail> tree[maxn];

trail mais_distante;
vector<trail> centros;

void dfs(int u, int tempo[], int pai[]) {
    
    if (tempo[u] > mais_distante.time) {

        mais_distante.time = tempo[u];
        mais_distante.node = u;
    }

    for (auto V:tree[u]) {

        int v = V.node;
        int t = V.time;

        if (v == pai[u]) continue;

        tempo[v] = tempo[u] + t;
        pai[v] = u;

        dfs(v, tempo, pai);
    }
}

trail backtrack(int node, int tempo[], int pai[]) {

    int diam = tempo[node];
    trail centro = {-1, (int) 2e9};

    while (node != -1) {

        int maior = max(tempo[node], diam - tempo[node]);

        if (maior < centro.time) 
            centro = {node, maior};

        node = pai[node];
    }

    centro.diam = diam;
    return centro;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
    for (int i = 0; i < M; i++) {

        tree[ A[i] ].push_back({B[i], T[i]});
        tree[ B[i] ].push_back({A[i], T[i]});
    }

    int tempo1[N];
    int tempo2[N];
    memset(tempo1, 0, sizeof(tempo1));
    memset(tempo2, 0, sizeof(tempo2));

    int pai1[N];
    int pai2[N];
    memset(pai1, -1, sizeof(pai1));
    memset(pai2, -1, sizeof(pai2));
    

    for (int i = 0; i < N; i++) {
        
        //Se i não faz parte duma árvore avaliada
        if (tempo1[i] == 0) {

            mais_distante = {-1, -1};
            
            //busca 1
            pai1[i] = -1;
            dfs(i, tempo1, pai1); 
            
            //busca 2
            pai2[mais_distante.node] = -1;
            mais_distante.time = -1;
            dfs(mais_distante.node, tempo2, pai2); //O caminho até o mais distante deste é o diâmetro

            centros.push_back(backtrack(mais_distante.node, tempo2, pai2)); //Achando o centro 
        }
        
   
    }

    //Agora vamos unir os centros!
    
    trail resposta = {centros[0].node, centros[0].time, centros[0].diam};
    for (int i = 1; i < (int) centros.size(); i++) {

        trail atual = centros[i];

        //O diâmetro é o maior entre o atual e a ligação nova

        if (resposta.diam < resposta.time + L + atual.time) { //Se o diãmetro antigo é menor

            resposta.diam = resposta.time + L + atual.time;

            //Qual deve ser o novo centro
            int op1 = max(resposta.diam - resposta.time - L, atual.time); //O nó novo?
            int op2 = max(resposta.diam - atual.time - L, resposta.time); //O antigo?

            if (op1 < op2) //Se precisa ser o nó novo
                resposta.node = atual.node, resposta.time = op1;

            else { //Se pode ser o atual
                resposta.time = op2;
            }
        }
    }

    return resposta.diam;
}

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