Submission #957068

#	Time	Username	Problem	Language	Result	Execution time	Memory
957068		MuntherCarrot	Traffic (IOI10_traffic)	C++14	50 / 100	328 ms	178552 KiB

traffic

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

using namespace std;

#define ll long long

const int MAXN = 1e6 + 10;
vector<vector<int>> vtx(MAXN);
ll a[MAXN], mx[MAXN];

ll dfs(int u, int p, ll cnt){
    ll sum = 0;
    mx[u] = cnt;
    for(int v : vtx[u]){
        if(v == p) continue;
        ll res = dfs(v, u, cnt + a[u]);
        mx[u] = max(mx[u], res);
        sum += res;
    }
    return sum + a[u];
}

int LocateCentre(int N, int P[], int S[], int D[]){
    for(int i = 0; i < N; i++){
        a[i] = P[i];
    }
    for(int i = 0; i < N - 1; i++){
        vtx[S[i]].push_back(D[i]);
        vtx[D[i]].push_back(S[i]);
    }
    dfs(0, 0, 0);
    int ans = 0;
    for(int i = 1; i < N; i++){
        if(mx[i] < mx[ans]){
            ans = i;
        }
    }
    return ans;
}

// by me

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