Submission #398512

#	Time	Username	Problem	Language	Result	Execution time	Memory
398512		iulia13	Traffic (IOI10_traffic)	C++14	100 / 100	1145 ms	174568 KiB

traffic

#include <iostream>
#include <vector>
#include "traffic.h"
using namespace std;
const int nmax = 1e6 + 5;
vector <int> g[nmax];
int dp[nmax];
int new_dp[nmax];
int v[nmax];
int minim = 2e9 + 5, sol;
int maxim[nmax];
#define pb push_back
void dfs(int nod, int dad = -1)
{
    dp[nod] = v[nod];
    for (auto x : g[nod])
    {
        if (dad == x)
            continue;
        dfs(x, nod);
        dp[nod] += dp[x];
        maxim[nod] = max(maxim[nod], dp[x]);
    }
}
int LocateCentre(int n, int p[], int s[], int d[])
{
    int sum = 0, i;
    for (i = 0; i < n - 1; i++)
    {
        g[s[i]].pb(d[i]);
        g[d[i]].pb(s[i]);
    }
    for (i = 0; i < n; i++)
        v[i] = p[i], sum += v[i];
    dfs(0);
    for (i = 0; i < n; i++)
    {
        maxim[i] = max(maxim[i], sum - dp[i]);
        if (minim > maxim[i])
        {
            minim = maxim[i];
            sol = i;
        }
    }
    return sol;
}/*
int p[nmax];
int s[nmax];
int d[nmax];
int main()
{
    int n, i;
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> p[i];
    for (i = 0; i < n - 1; i++)
        cin >> s[i] >> d[i];
    cout << LocateCentre(n, p, s, d);
    return 0;
}*/

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