Submission #671961

#	Time	Username	Problem	Language	Result	Execution time	Memory
671961		sudheerays123	Traffic (IOI10_traffic)	C++17	50 / 100	15 ms	2516 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 = 1000+5 , INF = 3e9 , MOD = 1e9+7;

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

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

	ll ans = -INF;

	for(auto u : adj[s]){
		if(u == par) continue;
		dfs(u,s,p);
		ans = max(ans,sub[u]+p[u]);
		sub[s] += sub[u]+p[u];
	}

	return ans;
}

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

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

	ll ans = INF , city;

	for(ll i = 0; i < N; i++){
		for(ll j = 0; j < N; j++) sub[j] = 0;
		ll x = dfs(i,-1,P);
		if(x < ans){
			ans = x;
			city = i;
		}
	}

	return city;
}

Compilation message (stderr)

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

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