Submission #669276

#	Time	Username	Problem	Language	Result	Execution time	Memory
669276		a_aguilo	Dreaming (IOI13_dreaming)	C++14	0 / 100	1082 ms	14008 KiB

dreaming

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

using namespace std;

vector<vector<int>> AdjList, Weights;
vector<int> component, Diameter;

void TreeDiameter(int root, int N){
    vector<int> distances(N, -1);
    distances[root] = 0;
    int maxNode = 0;
    queue<int> Q;
    Q.push(0);
    while(!Q.empty()){
        int nodeAct = Q.front(); Q.pop();
        if(distances[nodeAct] > distances[maxNode]) maxNode = nodeAct;
        for(int next = 0; next < AdjList[nodeAct].size(); ++next){
            int neighbour = AdjList[nodeAct][next];
            int time = Weights[nodeAct][next];
            if(distances[neighbour] != -1) continue;
            distances[neighbour] = distances[nodeAct] + time;
            component[neighbour] = component[nodeAct];
            Q.push(neighbour);
        }
    }
    distances = vector<int>(N, -1);
    distances[maxNode] = 0;
    Q.push(maxNode);
    while(!Q.empty()){
        int nodeAct = Q.front(); Q.pop();
        if(distances[nodeAct] > Diameter[root]) Diameter[root] = distances[nodeAct];
        for(int next = 0; next < AdjList[nodeAct].size(); ++next){
            int neighbour = AdjList[nodeAct][next];
            int time = Weights[nodeAct][next];
            if(distances[neighbour] != -1) continue;
            distances[neighbour] = distances[nodeAct] + time;
            Q.push(neighbour);
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    AdjList = vector<vector<int>>(N);
    Weights = vector<vector<int>>(N);
    for(int i = 0; i < M; ++i){
        AdjList[A[i]].push_back(B[i]);
        AdjList[B[i]].push_back(A[i]);
        Weights[B[i]].push_back(T[i]);
        Weights[A[i]].push_back(T[i]);
    }
    component = vector<int>(N, -1);
    Diameter = vector<int>(N, -1);
    for(int i = 0; i < N; ++i){
        if(component[i] == -1){
            component[i] = i;
            TreeDiameter(i, N);
        }
    }
    sort(Diameter.rbegin(), Diameter.rend());
    int MaxTravel = Diameter[0] + Diameter[1] + L;
    if((N-M-1) == 1) return MaxTravel;
    MaxTravel= max(MaxTravel, Diameter[1] + Diameter[2] + 2*L);
    return MaxTravel;
}

Compilation message (stderr)

dreaming.cpp: In function 'void TreeDiameter(int, int)':
dreaming.cpp:18:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int next = 0; next < AdjList[nodeAct].size(); ++next){
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:33:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int next = 0; next < AdjList[nodeAct].size(); ++next){
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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