Submission #585683

#	Time	Username	Problem	Language	Result	Execution time	Memory
585683		SeDunion	Game (IOI14_game)	C++17	42 / 100	102 ms	5088 KiB

game

#include "game.h"
#include<iostream>
#include<vector>
using namespace std;
 
const int N = 2000;
 
int frb[N][N];
int n;
 
void initialize(int n_) {
	n = n_;
	for (int i = 0 ; i < n ; ++ i) {
		for (int j = 0 ; j < n ; ++ j) {
			frb[i][j] = 0;
		}
	}
}
 
int used[N];
vector<int>g[N];
 
void dfs(int v) {
	used[v] = 1;
	for (int to : g[v]) if (!used[to]) {
		dfs(to);
	}
}
 
int hasEdge(int u, int v) {
  if (n > 80) {
return rand()%2;}
	for (int i = 0 ; i < n ; ++ i) {
		g[i].clear();
		used[i] = 0;
	}
	frb[u][v] = 1;
	frb[v][u] = 1;
	for (int i = 0 ; i < n ; ++ i) {
		for (int j = 0 ; j < i ; ++ j) {
			if (!frb[i][j]) {
				g[i].emplace_back(j);
				g[j].emplace_back(i);
			}
		}
	}
	dfs(v);
	if (used[u]) {
		return 0;
	} else {
		frb[u][v] = frb[v][u] = 0;
		return 1;
	}
}

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