Submission #235528

#	Time	Username	Problem	Language	Result	Execution time	Memory
235528		dolphingarlic	Traffic (IOI10_traffic)	C++14	100 / 100	1246 ms	178552 KiB

traffic

#include "traffic.h"

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

ll n, a[1000000], dp2[1000000], totsum = 0, ans = LLONG_MAX, city;
vector<ll> graph[1000000];
pair<ll, ll> dp1[1000000];

void dfs(ll node, ll parent = -1) {
    dp1[node] = {0, a[node]};
    for (ll i : graph[node]) {
        if (i == parent) continue;
        dfs(i, node);
        dp1[node].first = max(dp1[node].first, dp1[i].second);
        dp1[node].second += dp1[i].second;
    }
    dp2[node] = totsum - dp1[node].second;
    if (ans > max(dp1[node].first, dp2[node])) ans = max(dp1[node].first, dp2[node]), city = node;
}

int LocateCentre(int N, int A[], int S[], int D[]) {
    n = N;
    FOR(i, 0, n) {
        a[i] = A[i];
        totsum += a[i];
    }
    FOR(i, 0, n - 1) {
        graph[S[i]].push_back(D[i]);
        graph[D[i]].push_back(S[i]);
    }
    dfs(0);
    return city;
}

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