oj.uz

Submission #463696

# Submission time Handle Problem Language Result Execution time Memory
463696 2021-08-11T13:54:15 Z mshandilya Dreaming (IOI13_dreaming) C++14
18 / 100
 82 ms 15592 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(nodes, 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, -1);
    max_sub_dist[N] = 0;
    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 Incorrect 82 ms 15592 KB Output isn't correct
2 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 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9652 KB Output is correct
2 Correct 33 ms 9740 KB Output is correct
3 Correct 39 ms 9700 KB Output is correct
4 Correct 37 ms 9664 KB Output is correct
5 Correct 35 ms 9556 KB Output is correct
6 Correct 44 ms 10248 KB Output is correct
7 Correct 46 ms 10064 KB Output is correct
8 Correct 35 ms 9552 KB Output is correct
9 Correct 34 ms 9424 KB Output is correct
10 Correct 46 ms 9952 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 19 ms 10052 KB Output is correct
13 Correct 17 ms 10108 KB Output is correct
14 Correct 21 ms 10112 KB Output is correct
15 Correct 21 ms 10032 KB Output is correct
16 Correct 16 ms 10052 KB Output is correct
17 Correct 16 ms 10036 KB Output is correct
18 Correct 17 ms 10052 KB Output is correct
19 Correct 17 ms 10008 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 588 KB Output is correct
23 Correct 17 ms 10104 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 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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