제출 #726517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726517		hollwo_pelw	게임 (APIO22_game)	C++17	100 / 100	1298 ms	57476 KiB

game

#include "game.h"

#ifdef hollwo_pelw_local
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;

int n, k, tl[N], tr[N], res = 0;
vector<int> gi[N], go[N];

void init(int _n, int _k) {
	n = _n, k = _k;
	for (int i = 0; i < k; i++)
		tl[i] = tr[i] = i;
	for (int i = k; i < n; i++)
		tl[i] = tr[i] = i;
	for (int i = k; i < n; i++)
		tl[i] = -1, tr[i] = k;
}

inline int mid(int u) {
	return tl[u] + (tr[u] - tl[u]) / 2; // (tl[u] + tr[u]) / 2;
}

inline void debug(int u) {
	cout << "[" << tl[u] << ", " << mid(u) << "] -> " << u << " -> [" << mid(u) << ", " << tr[u] << "]" << endl;
}

inline int update(int u, int v) {
	if (tr[u] <= tl[v]) return 0;
	if (tl[u] >= tr[v]) return 1;

	// debug(u);
	// debug(v);

	while (mid(v) < tl[u]) {
		// cout << "UPDaTE " << v  << endl;
		// debug(v);
		tl[v] = mid(v) + 1;
		for (int x : go[v])
			if (update(v, x)) return 1;
	}

	while (mid(u) >= tr[v]) {
		// cout << "UpdAte " << u << endl;
		// debug(u);
		tr[u] = mid(u);
		for (int x : gi[u])
			if (update(x, u)) return 1;
	}

	return 0;
}

int add_teleporter(int u, int v) {
	if (v <= u && u < k)
		return 1;
	if (u == v) return 0;

	// cout << "ADD " << u << " -> " << v << endl;

	go[u].push_back(v);
	gi[v].push_back(u);

	return update(u, v);
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 40 / 40