Submission #410577

#	Time	Username	Problem	Language	Result	Execution time	Memory
410577		tht2005	Traffic (IOI10_traffic)	C++14	0 / 100	15 ms	23756 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];

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

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);
    for(int i = 0; i < n; ++i) {
        val[i] = max(val[i], sum - a[i] - val[i]);
    }
    return min_element(val, val + n) - val;
}

/* 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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25