oj.uz

답안 #384131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384131 2021-03-31T14:15:30 Z aaravdodhia Traffic (IOI10_traffic) C++17
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> val;
vector<vector<int>> adj;

// max_traffic = max(all traffic in node's subordinates)
// cur_traffic = traffic of node = sum of subordinate's traffic + val[node]

int DFS(int u, int p, int root){
    int max_traffic = 0, cur_traffic = val[u];

    for(int v : adj[u]){
        if(v == p) continue;
        int sub_traffic = DFS(v, u, root);
        max_traffic = max(max_traffic, sub_traffic);
        cur_traffic += sub_traffic;
    }

    if(u == root){
        return max_traffic;
    } else{
        return cur_traffic;
    }
}

int find_arena(){
    int arena = N, min_congestion = 2e9+1;

    for(int root = 0; root < N; root++){
        int max_traffic = DFS(root, -1, root);
        if(max_traffic < min_congestion){
            arena = root;
            min_congestion = max_traffic;
        }
    }

//    cout << min_congestion << endl;
    return arena;
}

void LocateCentre(int Nodes, int* P, int* S, int* D)
{
    N = Nodes;

    val.resize(N);
    for(int i=0; i<N; i++)
        val[i] = P[i];

    adj.resize(N);
    for(int i=0; i<N-1; i++){
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }

    cout << find_arena() << endl;
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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