Skip to Content
CTRL K

Ski Course Rating

Análisis oficial (C++) 

Explicación

Primero, notemos que una vaca puede moverse a lo largo de las aristas cuya diferencia de elevación es a lo sumo DD. Así, las celdas alcanzables desde un punto de partida son las celdas de su componente conexa en este grafo.

Luego, ordenamos todas las aristas por diferencia de elevación e iteramos sobre ellas en orden creciente, de forma similar al algoritmo de Kruskal, usando un DSU para mantener las componentes conexas. A medida que agregamos aristas, efectivamente aumentamos el DD permitido.

También mantenemos, para cada componente del DSU, la cantidad de puntos de partida en esa componente, de forma similar a cómo mantenemos los tamaños de las componentes del DSU.

Cuando una componente alcanza por primera vez un tamaño de al menos TT, el peso de la arista actual es exactamente la dificultad mínima requerida para que esa componente tenga tamaño ≥T\ge T. Por lo tanto, todos los puntos de partida en ella ya encontraron su dificultad mínima requerida, así que sumamos su contribución (cantidad de puntos de partida en la componente multiplicada por esta dificultad mínima) a la respuesta total y reiniciamos su conteo a 00 para no contar dos veces.

Implementación

Complejidad temporal: O(NMlog⁡(NM))\mathcal{O}(NM \log (NM))

import sys
 
sys.stdin = open("skilevel.in")
sys.stdout = open("skilevel.out", "w+")
 
 
# BeginCodeSnip{Disjoint Set Union}
class DisjointSets:
	def __init__(self, size: int) -> None:
		self.parents = [i for i in range(size)]
		self.sizes = [1 for _ in range(size)]
 
	def find(self, x: int) -> int:
		""":return: el nodo "representante" de la componente de x"""
		if self.parents[x] == x:
			return x
		self.parents[x] = self.find(self.parents[x])
		return self.parents[x]
 
	def unite(self, x: int, y: int) -> bool:
		""":return: si la fusión cambió la conectividad"""
		x_root = self.find(x)
		y_root = self.find(y)
		if x_root == y_root:
			return False
 
		if self.sizes[x_root] < self.sizes[y_root]:
			x_root, y_root = y_root, x_root
 
		self.parents[y_root] = x_root
		self.sizes[x_root] += self.sizes[y_root]
		return True
 
	def connected(self, x: int, y: int) -> bool:
		""":return: si x e y están en la misma componente conexa"""
		return self.find(x) == self.find(y)
 
 
# EndCodeSnip
 
n, m, t = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
waypoint_graph = [list(map(int, input().split())) for _ in range(n)]
 
waypoints = [i * m + j for i in range(n) for j in range(m) if waypoint_graph[i][j] == 1]
counts = [0] * (n * m)  # almacena la cantidad de puntos de partida para cada raíz del DSU
 
dsu = DisjointSets(n * m)
for i in waypoints:
	counts[i] = 1
 
edges = []
moves = [(0, 1), (1, 0)]
 
# crear aristas con pesos equivalentes a la diferencia de elevación
for i in range(n):
	for j in range(m):
		for x, y in moves:
			if 0 <= i + x < n and 0 <= j + y < m:
				edges.append(
					(
						i * m + j,
						(i + x) * m + (j + y),
						abs(grid[i + x][j + y] - grid[i][j]),  # peso de la arista
					)
				)
 
# ordenar las aristas en pesos crecientes para Kruskal
edges.sort(key=lambda x: x[2])
 
total = 0
for a, b, d in edges:
	root_a = dsu.find(a)
	root_b = dsu.find(b)
 
	if root_a != root_b:
		dsu.unite(a, b)
		root = dsu.find(a)
		counts[root] = counts[root_a] + counts[root_b]
 
		if dsu.sizes[root] >= t:
			total += counts[root] * d
			counts[root] = 0  # esta componente ya fue respondida
 
print(total)

Curiosamente, el siguiente código pasa todos los casos de prueba pero no pasaría si T=1T = 1; habría que hacer un caso especial para eso.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct Edge {
	int u, v, w;
};
 
struct DSU {
	vector<int> p, sz, unprocessed_starts;
	DSU(int n) : p(n), sz(n, 1), unprocessed_starts(n) { iota(p.begin(), p.end(), 0); }
 
	int get(int x) {
		if (p[x] != x) { p[x] = get(p[x]); }
		return p[x];
	}
 
	void unite(Edge e) {
		int a = get(e.u);
		int b = get(e.v);
		if (sz[a] < sz[b]) { swap(a, b); }
		if (a != b) {
			p[b] = a;
			sz[a] += sz[b];
			unprocessed_starts[a] += unprocessed_starts[b];
		}
	}
};
 
int main() {
	ifstream read("skilevel.in");
	int n, m, t;
	read >> n >> m >> t;
	vector<vector<int>> grid(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { read >> grid[i][j]; }
	}
	vector<vector<int>> is_start(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { read >> is_start[i][j]; }
	}
 
	auto to_int = [&](int r, int c) -> int { return r * m + c; };
 
	vector<Edge> edges;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// agregar una arista entre posiciones adyacentes
			if (i < n - 1) {
				edges.push_back(
				    {to_int(i, j), to_int(i + 1, j), abs(grid[i][j] - grid[i + 1][j])});
			}
			if (j < m - 1) {
				edges.push_back(
				    {to_int(i, j), to_int(i, j + 1), abs(grid[i][j] - grid[i][j + 1])});
			}
		}
	}
 
	// ordenar las aristas por peso
	sort(edges.begin(), edges.end(), [&](Edge a, Edge b) { return a.w < b.w; });
 
	DSU dsu(n * m);
 
	// inicializar en el dsu si este es un punto de partida
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (is_start[i][j]) { dsu.unprocessed_starts[to_int(i, j)] = 1; }
		}
	}
 
	ll ans = 0;
	for (Edge e : edges) {
		dsu.unite(e);
		int par = dsu.get(e.u);
		if (dsu.sz[par] >= t) {
			// sumar la cantidad de nodos de partida que no procesamos * peso actual
			ans += (ll)e.w * dsu.unprocessed_starts[par];
			// reiniciar los nodos de partida no procesados a 0
			dsu.unprocessed_starts[par] = 0;
		}
	}
 
	ofstream("skilevel.out") << ans << endl;
}
Fundamentos