Submission #1207686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207686		vanea	Traffic (IOI10_traffic)	C++20	100 / 100	455 ms	160884 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 1e6+10;

ll dp[mxN], pop[mxN];
vector<int> adj[mxN];
ll sum = 0;
ll ans = 1e18, last = -1;

void dfs(int node, int p) {
    for(auto it : adj[node]) {
        if(it == p) continue;
        dfs(it, node);
        dp[node] += dp[it];
    }
    dp[node] += pop[node];
    ll mx = sum-dp[node];
    for(auto it : adj[node]) {
        if(it == p) continue;
        mx = max(mx, dp[it]);
    }
    if(mx < ans) {
        ans = mx;
        last = node;
    }
}

int LocateCentre(int n, int p[], int s[], int d[]) {
    for(int i = 0; i < n-1; i++) {
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    for(int i = 0; i < n; i++) {
        sum += p[i];
        pop[i] = p[i];
    }
    dfs(0, -1);
    return last;
}
/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int p[10], s[10], d[10];
    for(int i = 0; i < n; i++) {
        cin >> p[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, p, s, d);
    return 0;
}*/

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