Submission #410581

#	Time	Username	Problem	Language	Result	Execution time	Memory
410581		tht2005	Traffic (IOI10_traffic)	C++14	100 / 100	1156 ms	168672 KiB

traffic

#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, int a[])
{
    res[u] = val[u] = 0;
    for(int v: adj[u]) {
        if(v != parent) {
            dfs1(v, u, a);
            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, a);
    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: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25