제출 #366905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366905		BlancaHM	Traffic (IOI10_traffic)	C++14	100 / 100	1291 ms	170732 KiB

traffic

#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;

ll dfs(int S, int padre, vector<vector<int>> & listaAdyacencia, vector<ll> & DP) {
	for (int v: listaAdyacencia[S]) {
		if (v == padre)
			continue;
		DP[S] += dfs(v, S, listaAdyacencia, DP);
	}
	// DP[S] contiene la suma de las poblaciones del subárbol de S
	return DP[S];
}

int LocateCentre(int N, int P[], int S[], int D[]) {
	vector<ll>DP(N);
	vector<vector<int>> listaAdyacencia(N, vector<int>());
	for (int i = 0; i < N-1; i++) {
		// pasamos el formato de entrada a una lista de adyacencia, más cómodo para operar
		// al ser aristas bidireccionales, las añadimos en ambas direcciones
		listaAdyacencia[S[i]].emplace_back(D[i]);
		listaAdyacencia[D[i]].emplace_back(S[i]);
	}
	for (int i = 0; i < N; i++)
		DP[i] = P[i]; // inicializamos la DP para que contenga la población de cada ciudad

	// rellenamos la DP
	dfs(0, -1, listaAdyacencia, DP);

	// por defecto, elegimos 0 como ciudad arbitrariamente y encontramos la máxima congestión
	int ciudadElegida = 0;
	ll maximaCongestionCiudadElegida = 0;
	for (int vecinoRaiz: listaAdyacencia[0]) {
		maximaCongestionCiudadElegida = max(maximaCongestionCiudadElegida, DP[vecinoRaiz]);
	}

	ll maximaCongestionCiudadActual;
	for (int ciudadActual = 1; ciudadActual < N; ciudadActual++) {
		maximaCongestionCiudadActual = DP[0] - DP[ciudadActual];
		for (int v: listaAdyacencia[ciudadActual]) {
			if (DP[v] < DP[ciudadActual])
				maximaCongestionCiudadActual = max(maximaCongestionCiudadActual, DP[v]);
		}
		if (maximaCongestionCiudadActual < maximaCongestionCiudadElegida) {
			maximaCongestionCiudadElegida = maximaCongestionCiudadActual;
			ciudadElegida = ciudadActual;
		}
	}
	return ciudadElegida;
}

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