Submission #878978

#	Time	Username	Problem	Language	Result	Execution time	Memory
878978		AverageAmogusEnjoyer	Traffic (IOI10_traffic)	C++17	0 / 100	9 ms	29188 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=1e6;
vector<int> adj[N];
ll dp[N];
ll sum[N];
void dfs0(int u=0,int e=-1) {
    for (int &v: adj[u]) if (v!=e) {
        dfs0(v,u);
        cmax(dp[u],sum[v]);
        sum[u]+=sum[v];
    }
}
void dfs1(int u=0,int e=-1) {
    for (int &v: adj[u]) if (v!=e) {
        cmax(dp[v],dp[0]-sum[v]);
        dfs1(v,u);
    }
}
int LocateCentre(int n, int _w[], int s[], int e[]) {
    for (int i=0;i<n-1;i++) {
        adj[s[i]].push_back(e[i]);
        adj[e[i]].push_back(s[i]);
    }
    for (int i=0;i<n;i++) {
        sum[i]=_w[i];
    }
    dfs0();
    dfs1();
    ll mx = 1e18;
    int res = -1;
    for (int i=0;i<n;i++) {
        if (cmin(mx,dp[i])) {
            res = i;
        }
    }
    assert(res!=-1);
    return res;
}

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