oj.uz

Submission #669879

# Submission time Handle Problem Language Result Execution time Memory
669879 2022-12-07T15:01:00 Z a_aguilo Dreaming (IOI13_dreaming) C++14
14 / 100
 78 ms 18648 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 64 ms 18648 KB Output is correct
2 Correct 64 ms 18252 KB Output is correct
3 Correct 40 ms 13864 KB Output is correct
4 Correct 7 ms 3024 KB Output is correct
5 Correct 6 ms 2004 KB Output is correct
6 Correct 13 ms 4344 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 26 ms 8124 KB Output is correct
9 Correct 38 ms 11200 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 62 ms 14076 KB Output is correct
12 Correct 78 ms 16220 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 18648 KB Output is correct
2 Correct 64 ms 18252 KB Output is correct
3 Correct 40 ms 13864 KB Output is correct
4 Correct 7 ms 3024 KB Output is correct
5 Correct 6 ms 2004 KB Output is correct
6 Correct 13 ms 4344 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 26 ms 8124 KB Output is correct
9 Correct 38 ms 11200 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 62 ms 14076 KB Output is correct
12 Correct 78 ms 16220 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 308 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 304 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Incorrect 1 ms 212 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11920 KB Output is correct
2 Correct 32 ms 11984 KB Output is correct
3 Correct 34 ms 11920 KB Output is correct
4 Correct 29 ms 11944 KB Output is correct
5 Correct 30 ms 11908 KB Output is correct
6 Correct 34 ms 12888 KB Output is correct
7 Correct 31 ms 12428 KB Output is correct
8 Correct 34 ms 11724 KB Output is correct
9 Correct 40 ms 11704 KB Output is correct
10 Correct 38 ms 12300 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 7 ms 8016 KB Output is correct
13 Correct 7 ms 8024 KB Output is correct
14 Correct 7 ms 8016 KB Output is correct
15 Correct 6 ms 8016 KB Output is correct
16 Correct 7 ms 8016 KB Output is correct
17 Correct 7 ms 8016 KB Output is correct
18 Correct 8 ms 8020 KB Output is correct
19 Correct 7 ms 8016 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 18648 KB Output is correct
2 Correct 64 ms 18252 KB Output is correct
3 Correct 40 ms 13864 KB Output is correct
4 Correct 7 ms 3024 KB Output is correct
5 Correct 6 ms 2004 KB Output is correct
6 Correct 13 ms 4344 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 26 ms 8124 KB Output is correct
9 Correct 38 ms 11200 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 62 ms 14076 KB Output is correct
12 Correct 78 ms 16220 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 308 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 304 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Incorrect 1 ms 212 KB Output isn't correct
29 Halted 0 ms 0 KB -