제출 #584542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584542		rainboy	게임 (APIO22_game)	C++17	2 / 100	1 ms	336 KiB

game

#include "game.h"
#include <stdlib.h>

const int N = 300000;

int *ej[N], eo[N], *fi[N], fo[N], ll[N], rr[N], n, k;

void append(int **ej, int *eo, int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

void init(int n_, int k_) {
	n = n_, k = k_;
	for (int i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		fi[i] = (int *) malloc(2 * sizeof *fi[i]);
	}
	for (int i = 0; i < n; i++)
		if (i < k)
			ll[i] = rr[i] = i;
		else
			ll[i] = -1, rr[i] = k;
}

int dfs1(int i, int l) {
	int o;
	if (ll[i] >= l)
		return 0;
	ll[i] = l;
	if (ll[i] > rr[i] || ll[i] == rr[i] && i >= k)
		return 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (dfs1(j, l))
			return 1;
	}
	return 0;
}

int dfs2(int j, int r) {
	int o;
	if (rr[j] <= r)
		return 0;
	rr[j] = r;
	if (ll[j] > rr[j] || ll[j] == rr[j] && j >= k)
		return 1;
	for (o = eo[j]; o--; ) {
		int i = fi[j][o];
		if (dfs2(i, r))
			return 1;
	}
	return 0;
}

int add_teleporter(int i, int j) {
	if (i == j)
		return i < k;
	append(ej, eo, i, j), append(fi, fo, j, i);
  return dfs1(j, ll[i]) || dfs2(i, rr[j]);
}

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

game.cpp: In function 'void append(int**, int*, int, int)':
game.cpp:10:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   10 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
game.cpp: In function 'int dfs1(int, int)':
game.cpp:33:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   33 |  if (ll[i] > rr[i] || ll[i] == rr[i] && i >= k)
      |                       ~~~~~~~~~~~~~~~^~~~~~~~~
game.cpp: In function 'int dfs2(int, int)':
game.cpp:48:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |  if (ll[j] > rr[j] || ll[j] == rr[j] && j >= k)
      |                       ~~~~~~~~~~~~~~~^~~~~~~~~

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