Skip to Content
CTRL K

Fennec VS. Snuke

Editorial oficial 

Explicación

De forma intuitiva, hay dos “fases” principales en esta pelea:

  1. Donde algunos nodos podrían volverse negros o blancos, y aún no está claro.
  2. Todos los nodos solo pueden volverse negros o blancos porque Fennec o Snuke los tienen bloqueados.

Mientras haya un nodo sin color en el único camino del nodo 11 al nodo NN, estamos en la fase 1. Después de eso, el árbol queda cortado en dos y cada nodo sin color solo puede alcanzar uno de los dos colores.

Así, tiene sentido que ambos jugadores intenten convertir a su color la mayor cantidad posible de nodos del camino antes de hacer cualquier otra cosa. Esto termina partiendo el camino en mitad negro y mitad blanco, y los caminos de longitud impar dan un nodo negro extra porque Fennec juega primero.

Después de esto, solo hay que ver qué jugador se reservó más territorio, porque ese es el que puede hacer más movimientos y superar a su oponente.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <functional>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int node_num;
	std::cin >> node_num;
	vector<vector<int>> neighbors(node_num);
	for (int i = 0; i < node_num - 1; i++) {
		int from, to;
		std::cin >> from >> to;
		neighbors[--from].push_back(--to);
		neighbors[to].push_back(from);
	}
 
	vector<int> parents(node_num);
	std::function<void(int, int)> calc_parents;
	calc_parents = [&](int at, int parent) {
		parents[at] = parent;
		for (int n : neighbors[at]) {
			if (n != parent) { calc_parents(n, at); }
		}
	};
	calc_parents(0, 0);
 
	// el camino de snuke a fennec (extremos incluidos)
	vector<int> path;
	int at = node_num - 1;
	while (at != 0) {
		path.push_back(at);
		at = parents[at];
	}
	path.push_back(0);
 
	// obtenemos los colores iniciales por los que realmente van a pelear
	vector<int> colors(node_num, -1);
	for (int i = 0; i < path.size(); i++) {
		// 0 = negro (fennec), 1 = blanco (snuke)
		colors[path[i]] = i < path.size() / 2;
	}
 
	// y por último vemos qué lado obtuvo más colores
	int diff = 0;  // fennec - snuke
	std::function<void(int)> fill_tree;
	fill_tree = [&](int at) {
		diff += colors[at] == 0 ? 1 : -1;
		for (int n : neighbors[at]) {
			if (n != parents[at]) {
				if (colors[n] == -1) { colors[n] = colors[at]; }
				fill_tree(n);
			}
		}
	};
	fill_tree(0);
 
	cout << (diff > 0 ? "Fennec" : "Snuke") << endl;
}
import java.io.*;
import java.util.*;
 
public class FennecVSSnuke {
	private static List<Integer>[] neighbors;
	private static int[] parents;
	private static int[] colors;
	private static int diff = 0;  // fennec - snuke
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int nodeNum = Integer.parseInt(read.readLine());
		neighbors = new List[nodeNum];
		for (int n = 0; n < nodeNum; n++) { neighbors[n] = new ArrayList<>(); }
		for (int i = 0; i < nodeNum - 1; i++) {
			StringTokenizer edge = new StringTokenizer(read.readLine());
			int from = Integer.parseInt(edge.nextToken()) - 1;
			int to = Integer.parseInt(edge.nextToken()) - 1;
			neighbors[from].add(to);
			neighbors[to].add(from);
		}
 
		parents = new int[nodeNum];
		calcParents(0, 0);
 
		// el camino de snuke a fennec (extremos incluidos)
		List<Integer> path = new ArrayList<>();
		int at = nodeNum - 1;
		while (at != 0) {
			path.add(at);
			at = parents[at];
		}
		path.add(0);
 
		// obtenemos los colores iniciales por los que realmente van a pelear
		colors = new int[nodeNum];
		Arrays.fill(colors, -1);
		for (int i = 0; i < path.size(); i++) {
			// 0 = negro (fennec), 1 = blanco (snuke)
			colors[path.get(i)] = i < path.size() / 2 ? 1 : 0;
		}
 
		// y por último vemos qué lado obtuvo más colores
		fillTree(0);
		System.out.println(diff > 0 ? "Fennec" : "Snuke");
	}
 
	private static void calcParents(int at, int parent) {
		parents[at] = parent;
		for (int n : neighbors[at]) {
			if (n != parent) { calcParents(n, at); }
		}
	}
 
	private static void fillTree(int at) {
		diff += colors[at] == 0 ? 1 : -1;
		for (int n : neighbors[at]) {
			if (n != parents[at]) {
				if (colors[n] == -1) { colors[n] = colors[at]; }
				fillTree(n);
			}
		}
	}
}
from sys import setrecursionlimit
 
setrecursionlimit(10**8)
 
 
def calc_parents(at: int, parent: int):
	parents[at] = parent
	for n in neighbors[at]:
		if n != parent:
			calc_parents(n, at)
 
 
def fill_tree(at: int):
	global diff
	diff += 1 if colors[at] == 0 else -1
	for n in neighbors[at]:
		if n != parents[at]:
			if colors[n] == -1:
				colors[n] = colors[at]
			fill_tree(n)
 
 
node_num = int(input())
neighbors = [[] for _ in range(node_num)]
for _ in range(node_num - 1):
	from_, to = [int(i) - 1 for i in input().split()]
	neighbors[from_].append(to)
	neighbors[to].append(from_)
 
parents = [0 for _ in range(node_num)]
calc_parents(0, 0)
 
# el camino de snuke a fennec (extremos incluidos)
path = []
at = node_num - 1
while at != 0:
	path.append(at)
	at = parents[at]
path.append(0)
 
colors = [-1 for _ in range(node_num)]
for i in range(len(path)):
	# 0 = negro (fennec), 1 = blanco (snuke)
	colors[path[i]] = int(i < len(path) // 2)
 
# y por último vemos qué lado obtuvo más colores
diff = 0  # fennec - snuke
fill_tree(0)
 
print("Fennec" if diff > 0 else "Snuke")
Fundamentos