Submission #533112

#	Time	Username	Problem	Language	Result	Execution time	Memory
533112		avaneeshk098	Traffic (IOI10_traffic)	C++17	100 / 100	906 ms	158952 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>


#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define max_size        100000000
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define w(t)			int t; cin >> t; while(t--)
#define inf             1e18
#define MOD				(int)1e9+7
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define range(a,b)      substr(a,b-a+1)
#define mina(a,b,c)		min(a, min(b, c))
#define maxa(a,b,c)		max(a, max(b, c))
#define sz(a)			(int)a.size()	
#define endl 			'\n'
#define trace(x)        cerr<<#x<<": "<<x<<" "<<endl;
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(x,y)		for(int i = x; i < y; i++)
// #define f(t)			int t; cin >> t; for(int i = 1; i <= t; i++)

using namespace std;

const int MXN = (int)1e6 + 5;
int dp1[MXN];
int dp2[MXN];
vi adj[MXN];
int cost[MXN];

int dfs(int s, int t){
	if(adj[s].size() == 1 && s != t){
		return cost[s];
	}
	for(auto i : adj[s]){
		if(i != t){
			int val = dfs(i,s);
			dp1[s] += val;
			dp2[s] = max(dp2[s], val);
		}
	}
	return dp1[s] + cost[s];
}

int LocateCentre(int n, int pp[], int s[], int d[]) {
	int total = 0;
	for(int i = 1; i <= n; i++){
		 cost[i] = pp[i-1];
		 total += cost[i];
	 }
	for(int i = 0; i < n-1; i++){
		adj[s[i]+1].pb(d[i]+1);
		adj[d[i]+1].pb(s[i]+1);
	} 
	dfs(1,1);
	int ans = inf;
	int fans;
	for(int i = 1; i <= n; i++){
		if(ans > max(total - dp1[i] - cost[i], dp2[i])){
			ans = max(total - dp1[i] - cost[i], dp2[i]);
			fans = i;
		}
	}
	return fans - 1;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:18:25: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | #define inf             1e18
      |                         ^~~~
traffic.cpp:65:12: note: in expansion of macro 'inf'
   65 |  int ans = inf;
      |            ^~~
traffic.cpp:73:16: warning: 'fans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  return fans - 1;
      |                ^

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