Submission #210907

#	Time	Username	Problem	Language	Result	Execution time	Memory
210907		socho	Traffic (IOI10_traffic)	C++14	100 / 100	1439 ms	143468 KiB

traffic

#include "traffic.h"
#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define int long long

const int MXN = 1000005;
int n;
int pop[MXN];
vector<int> adj[MXN];

int best[MXN];
int score[MXN];
int st_size[MXN];

int dfs_st(int node, int last) {
	st_size[node] = pop[node];
	for (int i=0; i<adj[node].size(); i++) {
		if (adj[node][i] == last) continue;
		st_size[node] += dfs_st(adj[node][i], node);
	}
	return st_size[node];
}

int ideal = 0;

void sco(int node, int last) {
	// cout << node << endl;
	int above = st_size[0] - st_size[node]; // stuff above
	for (int i=0; i<adj[node].size(); i++) {
		if (adj[node][i] == last) continue;
		above = max(above, st_size[adj[node][i]]);
	}
	score[node] = above;
	if (above < score[ideal]) ideal = node;
	for (int i=0; i<adj[node].size(); i++) {
		if (adj[node][i] == last) continue;
		sco(adj[node][i], node);
	}
}

int LocateCentre(int N, int P[], int S[], int D[]) {
	n = N;
	for (int i=0; i<n; i++) pop[i] = P[i];
	for (int i=0; i<n-1; i++) {
		adj[S[i]].push_back(D[i]);
		adj[D[i]].push_back(S[i]);
	}
	dfs_st(0, -1);
	sco(0, -1);
	return ideal;
}

Compilation message (stderr)

traffic.cpp: In function 'int dfs_st(int, int)':
traffic.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
traffic.cpp: In function 'void sco(int, int)':
traffic.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
traffic.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~

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