oj.uz

답안 #410580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410580 2021-05-23T03:34:17 Z tht2005 Traffic (IOI10_traffic) C++14
0 / 100
 16 ms 23756 KB 
#include <bits/stdc++.h>
using namespace std;

#define nmax 1000100

int n, sum, a[nmax], s[nmax], d[nmax];
vector <int> adj[nmax];

int val[nmax], res[nmax];

void dfs1(int u, int parent)
{
    res[u] = val[u] = 0;
    for(int v: adj[u]) {
        if(v != parent) {
            dfs1(v, u);
            val[u] += a[v] + val[v];
            res[u] = max(res[u], a[v] + val[v]);
        }
    }
    res[u] = max(res[u], sum - a[u] - val[u]);
}

int LocateCentre(int n, int a[], int s[], int d[])
{
    sum = 0;
    for(int i = 0; i < n; ++i)
        sum += a[i];
    for(int i = 0; i < n - 1; ++i) {
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    dfs1(0, 0);
    return min_element(res, res + n) - res;
}

/* int main()
 * {
 *     ios::sync_with_stdio(false); cin.tie(NULL);
 * 
 *     cin >> n;
 *     for(int i = 0; i < n; ++i)
 *         cin >> a[i];
 *     for(int i = 0; i < n - 1; ++i)
 *         cin >> s[i];
 *     for(int i = 0; i < n - 1; ++i)
 *         cin >> d[i];
 *     cout << LocateCentre(n, a, s, d) << '\n';
 * 
 *     return 0;
 * }
 */

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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