oj.uz

Submission #669276

# Submission time Handle Problem Language Result Execution time Memory
669276 2022-12-06T07:23:18 Z a_aguilo Dreaming (IOI13_dreaming) C++14
0 / 100
 1000 ms 14008 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 14008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 14008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 12292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 14008 KB Output isn't correct
2 Halted 0 ms 0 KB -