oj.uz

답안 #463697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
463697 2021-08-11T13:58:53 Z mshandilya 꿈 (IOI13_dreaming) C++14
18 / 100
 64 ms 15556 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(nodes, 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 15556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 15556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 9668 KB Output is correct
2 Correct 36 ms 9668 KB Output is correct
3 Correct 34 ms 9600 KB Output is correct
4 Correct 36 ms 9752 KB Output is correct
5 Correct 36 ms 9580 KB Output is correct
6 Correct 40 ms 10264 KB Output is correct
7 Correct 46 ms 10116 KB Output is correct
8 Correct 34 ms 9564 KB Output is correct
9 Correct 31 ms 9416 KB Output is correct
10 Correct 38 ms 10144 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 18 ms 10092 KB Output is correct
13 Correct 17 ms 10032 KB Output is correct
14 Correct 20 ms 10112 KB Output is correct
15 Correct 17 ms 10032 KB Output is correct
16 Correct 16 ms 10100 KB Output is correct
17 Correct 17 ms 10092 KB Output is correct
18 Correct 17 ms 10052 KB Output is correct
19 Correct 17 ms 10156 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 16 ms 10104 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 15556 KB Output isn't correct
2 Halted 0 ms 0 KB -