Submission #360252

#	Time	Username	Problem	Language	Result	Execution time	Memory
360252		sumit_kk10	Traffic (IOI10_traffic)	C++14	50 / 100	71 ms	19564 KiB

traffic

#include<traffic.h>
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
using namespace std;
const int N = 100000 + 5;
const int MOD = 1e9 + 7;
vector<int> graph[N];
long long int dis[N], mx[N], total;

void dfs(int source, int par, int p[]){
    for(auto k : graph[source]){
        if(k != par){
            dfs(k, source, p);
            dis[source] += dis[k];
            mx[source] = max(mx[source], dis[k]);
        }
    }
    mx[source] = max(mx[source], total - dis[source] - p[source]);
    dis[source] += p[source];
}

int LocateCentre(int n, int p[], int S[], int D[]){
    for(int i = 0; i < n - 1; ++i){
        graph[S[i]].push_back(D[i]);
        graph[D[i]].push_back(S[i]);
        total += p[i];
    }
    total += p[n - 1];
    dfs(0, -1, p);
    long long res = 0, ans = INT_MAX;
    for(int i = 0; i < n; ++i){
        if(mx[i] < ans){
            ans = mx[i];
            res = i;
        }
    }
    return res;
}
/*
5
10 10 10 20 20
0 2
1 2
2 3
3 4
 */

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