Submission #362986

#	Time	Username	Problem	Language	Result	Execution time	Memory
362986		vm152	Traffic (IOI10_traffic)	C++17	25 / 100	1119 ms	262148 KiB

traffic

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

#define ios ios_base::sync_with_stdio(0); cin.tie(0) ; cout.tie(0)
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define endl '\n'

typedef long long int ll ;

const int MAX = 1e6 ;
vector<ll> tree[MAX + 1] ;
vector<ll> cnt[MAX + 1] ;
ll sum = 0 ;

bool compare(vector<ll>& a, vector<ll>& b) {
	if (a[1] < b[1]) return 1 ;
	if (a[1] == b[1]) {
		int i = 2, j = 2 ;
		while (i < (int)a.size() && j < (int)b.size() && a[i] == b[j])
			i++ , j++ ;
		if (i >= (int)a.size()) return 1 ;
		if (j >= (int)b.size()) return 0 ;
		if (a[i] > b[j]) return 0 ;
		return 1 ;
	}
	return 0 ;
}

ll dfs(int node, int s, int p[]) {
	ll count = 0 ;
 	for (int i : tree[node]) {
 		if (i != s) {
		 	count = dfs(i, node, p) + p[i] ;
		 	cnt[node].eb(count) ;
 		}
 	}
 	ll sm = 0 ;
 	for (ll i : cnt[node]) sm += i ;
 	cnt[node].eb(sum - sm - p[node]) ;
 	return count ;
}

int LocateCentre(int n, int p[], int s[], int d[]) {
 	sum = 0 ;
 	for (int i = 0 ; i < n ; i++)
	 	sum += p[i] ; 
 	for (int i = 0; i < n - 1 ; i++) {
	 	tree[s[i]].eb(d[i]) ;
	 	tree[d[i]].eb(s[i]) ;
 	}
 	dfs(0, 0, p) ;
 	vector<vector<ll>> ans ;
 	for (int i = 0 ; i < n ; i++) { 
		 if (!cnt[i].empty()) {
		 	 sort(cnt[i].begin(), cnt[i].end()) ;
		 	 reverse(cnt[i].begin(), cnt[i].end()) ;
			 vector<ll> temp ;
			 temp.eb(i) ;
			 for (ll j : cnt[i]) temp.eb(j) ;
			 ans.eb(temp) ;
	     }
 	}
 	sort(ans.begin(), ans.end(), compare) ;
 	return ans[0][0] ;
}

/*
int main(){
	 ios ;
	 int n ;
	 cin >> n ;
	 int p[n] ;
	 int s[n] ;
	 int d[n] ;
	 for (int i = 0 ; i < n ; i++)
	 	 cin >> p[i] ;
	 for (int i = 0 ; i < n - 1 ; i++)
	 	 cin >> s[i] ;
	 for (int i = 0 ; i < n - 1 ; i++)
	 	 cin >> d[i] ;
	 int ans = LocateCentre(n, p, s, d) ;
	 cout << ans << endl ;
}
*/

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