oj.uz

Submission #669496

# Submission time Handle Problem Language Result Execution time Memory
669496 2022-12-06T14:53:14 Z a_aguilo Dreaming (IOI13_dreaming) C++14
0 / 100
 60 ms 17464 KB 
#include "dreaming.h"
#include<bits/stdc++.h>

using namespace std;

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];
    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;
    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());
    int MaxTravel = 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

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

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 60 ms 17464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11476 KB Output is correct
2 Correct 28 ms 11608 KB Output is correct
3 Correct 29 ms 11548 KB Output is correct
4 Correct 28 ms 11608 KB Output is correct
5 Correct 34 ms 11492 KB Output is correct
6 Correct 33 ms 12528 KB Output is correct
7 Correct 30 ms 12088 KB Output is correct
8 Correct 28 ms 11348 KB Output is correct
9 Correct 27 ms 11196 KB Output is correct
10 Correct 28 ms 11944 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 6 ms 8016 KB Output is correct
13 Correct 7 ms 8024 KB Output is correct
14 Correct 8 ms 8016 KB Output is correct
15 Correct 8 ms 8016 KB Output is correct
16 Correct 7 ms 8016 KB Output is correct
17 Correct 7 ms 7968 KB Output is correct
18 Correct 7 ms 8020 KB Output is correct
19 Correct 7 ms 8016 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 60 ms 17464 KB Output isn't correct
2 Halted 0 ms 0 KB -