Submission #954982

#	Time	Username	Problem	Language	Result	Execution time	Memory
954982		horiseun	Game (APIO22_game)	C++17	60 / 100	1304 ms	33776 KiB

game

#include <iostream>
#include <vector>
#include <algorithm>
#include "game.h"
using namespace std;

int n, k;
bool valid[30005][30005];
vector<int> adj[30005];

void init(int N, int K) {
	n = N;
	k = K;
	for (int i = 0; i < k; i++) {
		for (int j = i + 1; j < k; j++) {
			valid[i][j] = true;
		}
	}
}

bool dfs(int curr, int src) {
	if (curr <= src) return true;
	valid[src][curr] = true;
	for (int i : adj[curr]) {
		if (!valid[src][i] && dfs(i, src)) {
			return true;
		}
	}
	return false;
}

int add_teleporter(int u, int v) {
	for (int i = 0; i < k; i++) {
		if ((valid[i][u] || u == i) && dfs(v, i)) {
			return 1;	
		}
	}
	adj[u].push_back(v);
	return 0;
}

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