Submission #671964

#	Time	Username	Problem	Language	Result	Execution time	Memory
671964		sudheerays123	Traffic (IOI10_traffic)	C++17	100 / 100	893 ms	170772 KiB

traffic

#include "traffic.h"

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll int
const ll N = 1e6+5 , INF = 3e9 , MOD = 1e9+7;

vector<ll> adj[N] , sumdown(N) , maxdown(N);

void dfs(ll s , ll par , int p[]){

	for(auto u : adj[s]){
		if(u == par) continue;
		dfs(u,s,p);

		ll d = sumdown[u]+p[u];
		
		sumdown[s] += d;
		maxdown[s] = max(maxdown[s],d);
	}
}

int LocateCentre(int N, int P[], int S[], int D[]){

	ll total = 0;
	for(ll i = 0; i < N; i++) total += P[i];
	
	for(ll i = 0; i < N-1; i++){	
		adj[S[i]].push_back(D[i]);
		adj[D[i]].push_back(S[i]);
	}

	for(ll i = 0; i < N; i++){
		sumdown[i] = 0;
		maxdown[i] = -INF;
	}
	dfs(0,-1,P);

	ll ans = INF , city;

	for(ll i = 0; i < N; i++){
		ll d = maxdown[i];
		ll rest = total-sumdown[i]-P[i];

		if(max(d,rest) < ans){
			ans = max(d,rest);
			city = i;
		}
	}

	return city;
}

Compilation message (stderr)

traffic.cpp:7:28: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+9' to '2147483647' [-Woverflow]
    7 | const ll N = 1e6+5 , INF = 3e9 , MOD = 1e9+7;
      |                            ^~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:52:9: warning: 'city' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |  return city;
      |         ^~~~

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