제출 #577034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577034		Noam527	게임 (APIO22_game)	C++17	0 / 100	0 ms	208 KiB

game

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

int getbits(int cnt) {
	return (1 << cnt) - 1;
}

int n, k;
vector<vector<int>> g, grev;
vector<int> s, e;

void initial_colors(int layer, int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	for (int i = mid + 1; i <= r; i++)
		s[i] |= 1 << layer, e[i] |= 1 << layer;
	initial_colors(layer + 1, l, mid);
	initial_colors(layer + 1, mid + 1, r);
}

void init(int nn, int kk) {
	n = nn;
	k = kk;
	g.resize(n);
	grev.resize(n);
	s.resize(n);
	e.resize(n);

	initial_colors(0, 0, k - 1);
}

void forward_dfs(int layer, int need, int v) {
	if (e[v] & getbits(layer) != need) return;
	if (s[v] & (1 << layer)) return;
	s[v] |= 1 << layer;
	for (const auto &w : g[v])
		forward_dfs(layer, need, w);
}

void backward_dfs(int layer, int need, int v) {
	if (s[v] & getbits(layer) != need) return;
	if (~e[v] & (1 << layer)) return;
	e[v] ^= 1 << layer;
	for (const auto &w : grev[v])
		backward_dfs(layer, need, w);
}

int add(int layer, int l, int r, int u, int v) {
	if (l == r) return 0;
	if ((s[u] & (1 << layer)) && (~e[v] & (1 << layer))) return 1; // win
	if ((~s[u] & (1 << layer)) && (e[v] & (1 << layer))) return 0; // nothing more to discover...

	if (s[u] & (1 << layer))
		forward_dfs(layer, s[u] & getbits(layer), v);
	if (~e[v] & (1 << layer))
		backward_dfs(layer, e[v] & getbits(layer), u);

	int mid = (l + r) / 2;
	if (s[u] & (1 << layer))
		return add(layer + 1, mid + 1, r, u, v);
	return add(layer + 1, l, mid, u, v);
}

int add_teleporter(int u, int v) {
	g[u].push_back(v);
	grev[v].push_back(u);
	return add(0, 0, k - 1, u, v);
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'void forward_dfs(int, int, int)':
game.cpp:34:28: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   34 |  if (e[v] & getbits(layer) != need) return;
      |             ~~~~~~~~~~~~~~~^~~~~~~
game.cpp: In function 'void backward_dfs(int, int, int)':
game.cpp:42:28: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   42 |  if (s[v] & getbits(layer) != need) return;
      |             ~~~~~~~~~~~~~~~^~~~~~~

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