Submission #495544

#	Time	Username	Problem	Language	Result	Execution time	Memory
495544		PiejanVDC	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	332 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+1;
    }
    for(auto z : adj[u]) {
        if(z == e) continue;
        int nw = total[u] - total[z];
        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]-1].push_back(d[i]-1);
        adj[d[i]-1].push_back(s[i]-1);
    }
    root_dfs(0);
    dfs(0,0);
    return best;
}

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