Submission #499568

#	Time	Username	Problem	Language	Result	Execution time	Memory
499568		iwantin	Traffic (IOI10_traffic)	C++17	0 / 100	13 ms	23884 KiB

traffic

#include <bits/stdc++.h>
using namespace std;

#define M_PI 3.14159265358979323846 
#define pb push_back
#define fs first
#define sc second

typedef long long ll;
typedef long double ld;

const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 1;
const ll inf = 	LLONG_MAX;
const ll minf = LLONG_MIN; 

ll cost[maxn * 10], dist[maxn * 10],
children[maxn * 10], ans[maxn * 10];
vector <vector <ll> > g(maxn * 10);
bool used[maxn * 10];
ll n;

ll findChildren(ll v){
	used[v] = true;
	children[v] = 1;

	for(auto i: g[v])
		if(!used[i])
			children[v] += findChildren(i);

	return children[v];
}

ll findDist(ll v){
	used[v] = true;
	ll isZero = !(v == 0), num = 0;  

	ans[0] += cost[v] * children[v] * isZero;

	for(auto i: g[v])
		if(!used[i])
			num += findDist(i);

	dist[v] = num + cost[v] * children[v] * isZero;
	
	return dist[v];
}

void findAns(ll v, ll parent = -1){
	used[v] = true;

	if(parent != -1){
		ll mult = (n - children[v]);
		ans[v] = cost[parent] * mult + ans[parent];
		ans[v] -= cost[v] * (children[v]); 	  
	}  

	for(auto i: g[v])
		if(!used[i])
			findAns(i, v);

}

int LocateCentre (int n, int p[], int d[], int s[]){
	
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n;

	for(ll k = 0; k < n; k++)
		cost[k] = p[k];

	for(ll k = 0; k < n - 1; k++){
		ll a, b; a = s[k], b = d[k];
		g[a].pb(b);
		g[b].pb(a);
	} 

	findChildren(0); 

	for(ll k = 0; k < n; k++)
		used[k] = false;
	
	findDist(0);

	for(ll k = 0; k < n; k++)
		used[k] = false;
	
	findAns(0);
	
	ll mn = LLONG_MAX;
	int ansk = 0;

	for(int k = 0; k < n; k++){
		if(ans[k] < mn){
			mn = ans[k];
			ansk = k;
		}
	}

	return ansk;
}

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