Submission #128496

#	Time	Username	Problem	Language	Result	Execution time	Memory
128496		antimirage	Game (IOI14_game)	C++14	42 / 100	1072 ms	12792 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1505; 

int deg[N], used[N], cnt, n;

set <int> g[N];

void initialize(int N) {
	n = N;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			g[i].insert(j);
			g[j].insert(i);
		}
	}
}
void dfs (int v) {
	used[v] = 1;
	cnt++;
	
	for (auto to : g[v]) {
		if (used[to]) continue;
		dfs(to);
	}
}

int hasEdge(int u, int v) {
    u++;
    v++;
    assert(g[u].find(v) != g[u].end());
    assert(g[v].find(u) != g[v].end());
    g[u].erase(v);
    g[v].erase(u);
	memset(used, 0, sizeof(used) );
	cnt = 0;
    dfs(1);
    
    if (cnt < n) {
		g[v].insert(u);
		g[u].insert(v);
		return 1;
    }
    return 0;
}

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