Submission #1266053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266053		cordeiroalone	Dreaming (IOI13_dreaming)	C++20	100 / 100	66 ms	19136 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define MAX 100005
using ll = long long;

vector<pair<ll,int>> listaadj[MAX];
bool calculado[MAX];
vector<ll> centros;
int filhos[MAX];
ll distancias[MAX];
ll distlegal[MAX][2];
vector<int> arvoreatual;
ll maiorintra = 0;

void contaarvore(int x,int pai){
    arvoreatual.push_back(x);
    calculado[x] = 1;
    for(auto v : listaadj[x]){
        if(v.second == pai) continue;
        contaarvore(v.second,x);
    }
}

void dfs(int x,int pai,int modo){
    for(auto v : listaadj[x]){
        if(v.second == pai) continue;
        distlegal[v.second][modo] = distlegal[x][modo] + v.first;
        dfs(v.second,x,modo);
    }
}   

void calcularcentro(int x){
    distlegal[x][0] = 0;
    contaarvore(x,-1);
    dfs(x,-1,0);
    ll maiordist = 0,maiorid = x;
    for(auto v : arvoreatual){
        if(distlegal[v][0] > maiordist){
            maiordist = distlegal[v][0];
            maiorid = v;
        }
    }
    distlegal[maiorid][0] = 0;
    dfs(maiorid,-1,0);
    ll maiordist2 = 0,maiorid2 = maiorid;
    for(auto v : arvoreatual){
        if(distlegal[v][0] > maiordist2){
            maiordist2 = distlegal[v][0];
            maiorid2 = v;
        }
    }
    distlegal[maiorid2][1] = 0;
    maiorintra = max(maiorintra,maiordist2);
    dfs(maiorid2,-1,1);
    ll menortotal = INT64_MAX;
    for(auto v : arvoreatual){
        menortotal = min(menortotal,max(distlegal[v][0],distlegal[v][1]));
    }
    vector<int> temp;
    swap(temp,arvoreatual);
    centros.push_back(menortotal);
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i = 0; i < M; i++){
        int a = A[i],b = B[i],w = T[i];
        listaadj[a].push_back({w,b});
        listaadj[b].push_back({w,a});
    }
    for(int i = 0; i < N; i++){
        if(calculado[i])continue;
        calcularcentro(i);
    }
    sort(centros.begin(),centros.end());
    int tamcentros = centros.size();
    if(tamcentros == 1){
        return(maiorintra);
    }else if(tamcentros == 2){
        return(max(centros[tamcentros - 1] + centros[tamcentros - 2] + L,maiorintra));
    }else{
        return(max(max(centros[tamcentros - 1] + centros[tamcentros - 2] + L, centros[tamcentros - 2] + centros[tamcentros - 3] + (2 * L)),maiorintra));
    }
}

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