Submission #362965

#	Time	Username	Problem	Language	Result	Execution time	Memory
362965		vm152	Traffic (IOI10_traffic)	C++17	25 / 100	1168 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'

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

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

int dfs(int node, int s, int p[]) {
	int count = 0 ;
 	for (int i : tree[node]) {
 		if (i != s) {
		 	count = dfs(i, node, p) + p[i] ;
		 	cnt[node].eb(count) ;
 		}
 	}
 	long long sm = 0 ;
 	for (int 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<int>> 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<int> temp ;
			 temp.eb(i) ;
			 for (int 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 ;
}
*/

Compilation message (stderr)

traffic.cpp: In function 'bool compare(std::vector<int>&, std::vector<int>&)':
traffic.cpp:20:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while (i < a.size() && j < b.size() && a[i] == b[i])
      |          ~~^~~~~~~~~~
traffic.cpp:20:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while (i < a.size() && j < b.size() && a[i] == b[i])
      |                          ~~^~~~~~~~~~
traffic.cpp:22:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if (i >= a.size()) return 1 ;
      |       ~~^~~~~~~~~~~
traffic.cpp:23:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   if (j >= b.size()) return 0 ;
      |       ~~^~~~~~~~~~~

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