Submission #292659

#	Time	Username	Problem	Language	Result	Execution time	Memory
292659		7_7_7	Traffic (IOI10_traffic)	C++17	100 / 100	1277 ms	174700 KiB

traffic

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

using namespace std;

const int N = 1e6 + 7;

int val[N];
long long ans;
long long total;
long long sub[N];
vector<int> g[N];
long long best = LLONG_MAX;
void dfs(int v, int p){
    long long mx = 0;
    long long curSum = val[v];
    for(auto to: g[v]){
        if(to == p) continue;
        dfs(to, v);
        mx = max(mx, sub[to]);
        curSum += sub[to];
    }
    mx = max(mx, total - curSum);
    if(mx < best){
        best = mx;
        ans = v;
    }
    sub[v] = curSum;
}
int LocateCentre(int n, int p[N], int s[N], int d[N]){
    for(int i = 0; i < n; i ++){
        total += p[i];
        val[i] = p[i];
        if(i < n - 1){
            g[s[i]].push_back(d[i]);
            g[d[i]].push_back(s[i]);
        }
    }
    dfs(0, 0);
    return ans;
}

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