oj.uz

Submission #463688

# Submission time Handle Problem Language Result Execution time Memory
463688 2021-08-11T13:41:37 Z mshandilya Dreaming (IOI13_dreaming) C++14
18 / 100
 69 ms 16768 KB 
#include "bits/stdc++.h"
#include "dreaming.h"
#define adj_list vector<list<pair<int, int>>>
#define vi vector<int>
using namespace std;

int nodes;
adj_list adj;
vi max_sub_dist, final_dist, trees;

void dfs1(int root) {
    max_sub_dist[root] = 0;
    for(auto& i : adj[root]) {
        if(max_sub_dist[i.first]==-1) {
            dfs1(i.first);
            max_sub_dist[root] = max(max_sub_dist[root], max_sub_dist[i.first] + i.second);
        }
    }
}

int dfs2(int root) {
    pair<int, int> maxi = make_pair(0, 0), smaxi = make_pair(0, 0);
    for(auto& i : adj[root]) {
        if(max_sub_dist[i.first]+i.second > max_sub_dist[maxi.first] + maxi.second) {
            smaxi = maxi;
            maxi = i;
        }
    }
    if(max_sub_dist[smaxi.first] + smaxi.second >= max_sub_dist[maxi.first])
        return root;
    max_sub_dist[maxi.first] = max(max_sub_dist[maxi.first], max_sub_dist[smaxi.first] + smaxi.second + maxi.second);
    max_sub_dist[root] = max_sub_dist[smaxi.first] + smaxi.second;
    return dfs2(maxi.first);
}

int diameter_dfs(int root, int state = 0) {
    int maxi = root, node;
    final_dist[root] = 0;
    for(auto& i : adj[root]) {
        if(final_dist[i.first]==-1) {
            node = diameter_dfs(i.first, 1);
            if(i.second + final_dist[i.first] > final_dist[root]) {
                maxi = node;
                final_dist[root] = i.second + final_dist[i.first];
            }
        }
    }
    if(state)
        return maxi;
    final_dist.assign(nodes, -1);
    diameter_dfs(maxi, 1);
    return maxi;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    nodes = N;
    ///constructing adjacency list --> O(N+M) ~ O(2N)
    adj.assign(N, list<pair<int, int>> ());
    for(int i = 0; i<M; i++) {
        adj[A[i]].push_back(make_pair(B[i], T[i]));
        adj[B[i]].push_back(make_pair(A[i], T[i]));
    }
    ///finding the longest existing path from any node and selecting the minimum of those within a connected tree
    ///--> in order to find the longest path and simultaneously select, let us do two dfs such that the first
    /// finds max distance in the subtree and the second finds the overall max distance O(6N)
    max_sub_dist.assign(N, -1);
    int maxi = 0, node;
    for(int i = 0; i<N; i++) {
        if(max_sub_dist[i]==-1) {
            dfs1(i);
            node = dfs2(i);
            if(max_sub_dist[node]>max_sub_dist[maxi])
                maxi = node;
            trees.push_back(node);
        }
    }
    ///since now, we already know the trees that exist, we just need to optimally merge them
    for(int & tree : trees) {
        if(tree!=maxi) {
            adj[tree].push_back(make_pair(maxi, L));
            adj[maxi].push_back(make_pair(tree, L));
        }
    }
    ///now that the trees are merged, let's just find the maximum distance (tree diameter), between any two nodes
    final_dist.assign(N, -1);
    node = diameter_dfs(maxi);
    return final_dist[node];
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 15528 KB Output is correct
2 Correct 64 ms 16768 KB Output is correct
3 Correct 38 ms 11300 KB Output is correct
4 Correct 8 ms 2764 KB Output is correct
5 Correct 7 ms 1868 KB Output is correct
6 Correct 15 ms 3864 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 15528 KB Output is correct
2 Correct 64 ms 16768 KB Output is correct
3 Correct 38 ms 11300 KB Output is correct
4 Correct 8 ms 2764 KB Output is correct
5 Correct 7 ms 1868 KB Output is correct
6 Correct 15 ms 3864 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 9664 KB Output is correct
2 Correct 42 ms 10104 KB Output is correct
3 Correct 43 ms 10064 KB Output is correct
4 Correct 42 ms 10172 KB Output is correct
5 Correct 38 ms 10100 KB Output is correct
6 Correct 56 ms 10700 KB Output is correct
7 Correct 36 ms 10608 KB Output is correct
8 Correct 36 ms 9908 KB Output is correct
9 Correct 40 ms 9896 KB Output is correct
10 Correct 42 ms 10436 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 16 ms 9992 KB Output is correct
13 Correct 20 ms 10092 KB Output is correct
14 Correct 16 ms 10000 KB Output is correct
15 Correct 22 ms 10052 KB Output is correct
16 Correct 18 ms 10052 KB Output is correct
17 Correct 18 ms 10064 KB Output is correct
18 Correct 23 ms 10100 KB Output is correct
19 Correct 18 ms 10052 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 284 KB Output is correct
22 Correct 1 ms 588 KB Output is correct
23 Correct 16 ms 10052 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 15528 KB Output is correct
2 Correct 64 ms 16768 KB Output is correct
3 Correct 38 ms 11300 KB Output is correct
4 Correct 8 ms 2764 KB Output is correct
5 Correct 7 ms 1868 KB Output is correct
6 Correct 15 ms 3864 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -