Submission #205400

#	Time	Username	Problem	Language	Result	Execution time	Memory
205400		jasony123123	Traffic (IOI10_traffic)	C++11	100 / 100	1875 ms	170872 KiB

traffic

#include "traffic.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

v<int> adj[1000000];
ll sum[1000000];
pair<ll, int> ans = {LLONG_MAX, -1};

ll solve(int x, int p, int pp[], ll t){
	ll mymax = 0;
	sum[x] = pp[x];
	for(auto c : adj[x]) if(c!=p){
		ll csum = solve(c,x,pp,t);
		maxx(mymax, csum);
		sum[x] += csum;
	}
	maxx(mymax, t-sum[x]);
	minn(ans, {mymax, x});
	return sum[x];
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	ll total = 0;
	FOR(i,0,N){
		adj[S[i]].push_back(D[i]);
		adj[D[i]].push_back(S[i]);
		total += pp[i];
	}
	solve(0,-1, pp, total);
	return ans.second;
}

/*
0-n-1
pp is number
S-D
*/

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