Submission #1309931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309931		lativ	Dreaming (IOI13_dreaming)	C++20	100 / 100	44 ms	16332 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!
    
    sort(centros.begin(), centros.end(), [](trail a, trail b) { return a.time > b.time; });

    int resposta = centros[0].diam;

    if (centros.size() > 1) resposta = max(resposta, centros[0].time + L + centros[1].time);
    if (centros.size() > 2) resposta = max(resposta, centros[1].time + L + L + centros[2].time);

    return resposta;
}

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