oj.uz

답안 #341734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341734 2020-12-30T20:00:57 Z ProUG Traffic (IOI10_traffic) C++14
0 / 100
 15 ms 23812 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1000000];
int population_cumulative[1000000];
int population[1000000];
int highest_traffic[1000000];

int calculate_population (int node, int parent) {
    int total_population = population[node];
    for (auto child : adj[node]) {
        if (child != parent) {
            total_population += calculate_population(child, node);
        }
    }

    population_cumulative[node] = total_population;
    return total_population;
}

void dfs (int node, int parent, int overload) {
    int current_ans = overload;
    int children_population = 0;

    for (auto child : adj[node]) {
        if (child != parent) {
            children_population += population_cumulative[child];
            current_ans = max(current_ans, population_cumulative[child]);
        }
    }

    highest_traffic[node] = current_ans;

    for (auto child : adj[node]) {
        if (child != parent) {
            dfs(child, node, overload + population[node] + children_population - population_cumulative[child]);
        }
    }
}

int LocateCentre (int n, int p[], int d[], int s[]) {
    int root = 0;
    for (int i = 0; i < n; i++) {
        population[i] = p[i];
    }

    for (int i = 0; i < n-1; i++) {
        int a, b;
        a = d[i];
        b = s[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    calculate_population(root, -1);
    dfs(root, -1, 0);

    int lowest_traffic = INT_MAX, lowest_index = 0;
    for (int i = 0; i < n; i++) {
        cout << highest_traffic[i] << endl;
        if (highest_traffic[i] < lowest_traffic) {
            lowest_traffic = highest_traffic[i];
            lowest_index = i;
        }
    }

    return lowest_index;
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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