Submission #866703

#	Time	Username	Problem	Language	Result	Execution time	Memory
866703		Bula	Traffic (IOI10_traffic)	C++17	100 / 100	903 ms	163084 KiB

traffic

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

const int N = 1e6 + 5;
vector<long long> subtree(N), c(N);
vector<int> v[N];
long long ans = LLONG_MAX, sum = 0;
int pas;

void dfs1(int u, int par){
    subtree[u] = c[u];
    for(auto x : v[u]){
        if(x == par) continue;
        dfs1(x, u);
        subtree[u] += subtree[x];
    }
}


void dfs2(int u, int par){
    long long mx = 0;
    mx = max(mx, sum - subtree[u]);
    for(auto x : v[u]){
        if(x != par){
            mx = max(mx, subtree[x]);
            dfs2(x, u);
        }
    }
    if(mx < ans){
        ans = mx;
        pas = u;
    }
}

int LocateCentre(int n, int p[], int s[], int d[]){
    for(int i = 0; i < n; i++){
        c[i] = p[i];
        sum += p[i];
        if(i == n - 1) continue;
        v[s[i]].push_back(d[i]);
        v[d[i]].push_back(s[i]);
    }
    dfs1(0, -1);
    dfs2(0, -1);
    return pas;
}

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