Submission #360253

#	Time	Username	Problem	Language	Result	Execution time	Memory
360253		sumit_kk10	Traffic (IOI10_traffic)	C++14	100 / 100	1185 ms	194328 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 = 1000000 + 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: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25