Submission #425231

#	Time	Username	Problem	Language	Result	Execution time	Memory
425231		KhoaHo	Traffic (IOI10_traffic)	C++11	100 / 100	1086 ms	174588 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>

using namespace std;
int a[int(1e6) + 1], f[int(1e6) + 1], b[int(1e6) + 1];
vector<int> G[int(1e6) + 1];
int sum = 0;
void dfs(int u, int s)
{
    for(auto v : G[u])
    {
        if(v != s)
        {
            dfs(v, u);
            f[u] += f[v];
            b[u] = max(b[u], f[v]);
        }
    }
    b[u] = max(b[u], sum - f[u] - a[u]);
    f[u] += a[u];
}
int LocateCentre(int n, int p[], int s[], int d[])
{
    int res = -1, tmp = INT_MAX;
    for(int i = 0; i < n; i++)
    {
        sum += p[i];
        a[i] = p[i];
    }
    for(int i = 0; i < n - 1; i++)
    {
        G[d[i]].push_back(s[i]);
        G[s[i]].push_back(d[i]);
    }
    dfs(0, -1);
    for(int i = 0; i < n; i++)
    {
        if(b[i] < tmp)
        {
            tmp = b[i];
            res = i;
        }
    }
    return res;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25