Submission #669879

#	Time	Username	Problem	Language	Result	Execution time	Memory
669879		a_aguilo	Dreaming (IOI13_dreaming)	C++14	14 / 100	78 ms	18648 KiB

dreaming

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

using namespace std;

int diameter;
vector<vector<int>> AdjList, Weights;
vector<int> component, father, distFather, LongestDepth, NodeForLongestDepth, SecondLongestDepth;

void dfs(int node){
    LongestDepth[node] = 0;
    SecondLongestDepth[node] = 0;
    for(int next = 0; next < AdjList[node].size(); ++next){
        int neighbour = AdjList[node][next];
        int time = Weights[node][next];
        if(neighbour == father[node]) continue;
        father[neighbour] = node;
        distFather[neighbour] = time;
        component[neighbour] = component[node];
        dfs(neighbour);
        int DepthNeighbour = LongestDepth[neighbour] + time;
        if(DepthNeighbour >= LongestDepth[node]){
            SecondLongestDepth[node] = LongestDepth[node];
            LongestDepth[node] = DepthNeighbour;
            NodeForLongestDepth[node] = neighbour;
        }else if(DepthNeighbour >= SecondLongestDepth[node]){
            SecondLongestDepth[node] = DepthNeighbour;
        }
    }
}

int getDepthComponent(int node){
    
    if(father[node] != node){
        int predecesor = father[node];
        int optative = 0;
        if(node != NodeForLongestDepth[predecesor]) optative = LongestDepth[predecesor]+distFather[node];
        else optative = SecondLongestDepth[predecesor]+distFather[node];
        if(optative >= LongestDepth[node]){
            SecondLongestDepth[node] = LongestDepth[node];
            LongestDepth[node] = optative;
            NodeForLongestDepth[node] = predecesor;
        }else if(optative >= SecondLongestDepth[node]) SecondLongestDepth[node] = optative;
    }
    int ans = LongestDepth[node];
    diameter = max(diameter, ans);
    for(int neighbour: AdjList[node]) {
        if(neighbour != father[node])ans = min(ans, getDepthComponent(neighbour));
    }
    return ans;
}

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);
    LongestDepth = vector<int>(N, -1);
    SecondLongestDepth = vector<int> (N, -1);
    NodeForLongestDepth = vector<int>(N, -1);
    distFather = vector<int>(N, 1);
    father = vector<int>(N, -1);
    vector<int> depthsComponents;
    diameter = 0;
    for(int i = 0; i < N; ++i){
        if(component[i] == -1){
            component[i] = i;
            distFather[i] = 0;
            father[i] = i;
            dfs(i);
            depthsComponents.push_back(getDepthComponent(i));
        }
    }
    sort(depthsComponents.rbegin(), depthsComponents.rend());
    if(M == 0) return diameter;
    int MaxTravel = max(diameter, depthsComponents[0] + depthsComponents[1] + L);
    if((N-M-1) == 1) return MaxTravel;
    MaxTravel= max(MaxTravel, depthsComponents[1] + depthsComponents[2] + 2*L);
    return MaxTravel;
}

Compilation message (stderr)

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

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