Submission #495547

#	Time	Username	Problem	Language	Result	Execution time	Memory
495547		PiejanVDC	Traffic (IOI10_traffic)	C++17	100 / 100	1174 ms	174672 KiB

traffic

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

vector<vector<int>>adj;
int n;
vector<int>v;

vector<int>mx,total;

int root_dfs(int u, int e = -1) {
    int w = v[u];
    for(auto z : adj[u]) {
        if(z == e) continue;
        int curr = root_dfs(z,u);
        w+=curr;
        mx[u] = max(mx[u],curr);
    }
    return total[u] = w;
}

int best, mn = INT_MAX;

void dfs(int u, int sum, int e = -1) {
    if(max(mx[u],sum) < mn) {
        mn = max(mx[u],sum);
        best = u;
    }
    for(auto z : adj[u]) {
        if(z == e) continue;
        int nw = total[u] - total[z] + sum;
        dfs(z,nw,u);
    }
}

int LocateCentre(int nn, int p[], int s[], int d[]) {
    n=nn;
    adj.resize(n);
    v.resize(n);
    for(int i = 0 ; i < n ; i++) v[i] = p[i];
    mx.resize(n,0);
    total.resize(n,0);
    for(int i = 0 ; i < n-1 ; i++) {
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    root_dfs(0);
    dfs(0,0);
    return best;
}

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