Submission #330850

#	Time	Username	Problem	Language	Result	Execution time	Memory
330850		man_in_danger	Traffic (IOI10_traffic)	C++14	100 / 100	1866 ms	241284 KiB

traffic

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")

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

#define pb push_back
#define mk make_tuple
#define f first
#define s second

#define speedup ios_base::sync_with_stdio(false); cin.tie(NULL); 

typedef long long ll;
typedef pair<int, int> PII;

const ll mod = 1e9+7;
const ll inf = 1e18;
const int inf2 = 1e9;

vector<int> adj[1000005];
vector<ll> v[1000005];
int vis[1000005], d[1000005];
ll tot;

ll dfs1(int u){
	vis[u] = 1;
	ll ret = 0;
	for(int i = 0; i < adj[u].size(); i++){
		int ve = adj[u][i];
		if(!vis[ve]){
			ll r = dfs1(ve);
			ret += r;
			v[u].pb(r);
			//cout << u << " " << ve << " " << r << "\n";
		}
	}
	ret += d[u];
	return ret;
}
ll dfs2(int u){
	vis[u] = 1;
	ll ret = 0;
	for(int i = 0; i < adj[u].size(); i++){
		int ve = adj[u][i];
		if(!vis[ve]){
			ll r = dfs2(ve);
			ret += r;
			v[ve].pb(tot - r);
		}
	}
	ret += d[u];
	return ret;
}

int LocateCentre(int N, int P[], int S[], int D[]){
	int i, j;
	for(i = 0; i < N - 1; i++){
		adj[S[i]].pb(D[i]);
		adj[D[i]].pb(S[i]);
		d[i] = P[i];
	}
	d[i] = P[i];
	tot = dfs1(0);
	memset(vis, 0, sizeof vis);
	dfs2(0);
	ll mi = inf;
	int ans = 0;
	for(i = 0; i < N; i++){
		ll mx = 0;
		for(j = 0; j < v[i].size(); j++){
			mx = max(v[i][j], mx);
		}
		if(mx < mi){
			mi = mx;
			ans = i;
		}
	}
	return ans;
}

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

Compilation message (stderr)

traffic.cpp: In function 'll dfs1(int)':
traffic.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < adj[u].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
traffic.cpp: In function 'll dfs2(int)':
traffic.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0; i < adj[u].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(j = 0; j < v[i].size(); j++){
      |              ~~^~~~~~~~~~~~~

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