Submission #38655

#	Time	Username	Problem	Language	Result	Execution time	Memory
38655		14kg	Game (IOI14_game)	C++11	100 / 100	569 ms	9932 KiB

game

// SB Solution
#include "game.h"
#define N 1501
#define M 2048

int n, nn, d[M*2], tree_cnt[M*2];

void initialize(int _n) {
	n = _n;
	for (nn = 1; nn < n; nn *= 2);
	
	for (int i = 1; i <= n; i++) tree_cnt[nn + i - 1] = 1;
	for (int i = nn - 1; i >= 1; i--) {
		tree_cnt[i] = tree_cnt[i * 2] + tree_cnt[i * 2 + 1];
		d[i] = tree_cnt[i * 2] * tree_cnt[i * 2 + 1];
	}
}

int hasEdge(int x, int y) {
	x += nn, y += nn;
	while (x != y) {
		if (x > y) x /= 2;
		else y /= 2;
	} d[x]--;
	
	return d[x] ? 0 : 1;
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58