Submission #314756

#	Time	Username	Problem	Language	Result	Execution time	Memory
314756		wind_reaper	Traffic (IOI10_traffic)	C++17	50 / 100	441 ms	61352 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> edges;
int LocateCentre(int n, int p[], int s[], int d[]){
	edges.resize(n);

	vector<int> pref(n);

	pref[0] = p[0];

	for(int i = 1; i < n; i++)
		pref[i] = pref[i-1] + p[i];

	vector<int> suf(n);

	suf[n-1] = p[n-1];

	for(int i = n-2; i >= 0; --i)
		suf[i] = suf[i+1] + p[i];


	int centre = 0;
	int cur_min = 1e9;

	for(int i = 0; i < n; i++){
		if(max(pref[i] - p[i], suf[i] - p[i]) < cur_min){
			centre = i;
			cur_min = max(pref[i] - p[i], suf[i] - p[i]);
		}
	}

	return centre;
}

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