Submission #360934

#	Time	Username	Problem	Language	Result	Execution time	Memory
360934		jesus_coconut	Game (IOI14_game)	C++17	42 / 100	1093 ms	4864 KiB

game

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

using namespace std;

int const N = 1510;

int adj[N][N];
int n;
void initialize(int n) {
	::n = n;
	for (int i = 0; i < n; ++i) {
		adj[i][i] = 1;
	}
}

bitset<N> bio;
void floodFill(int ver) {
	bio[ver] = true;
	for (int i = 0; i < n; ++i) {
		if (!bio[i] && adj[ver][i] == 1) {
			floodFill(i);
		}
	}
}

vector<int> getConnected(int ver) {
	bio.reset();
	floodFill(ver);
	vector<int> ret;
	for (int i = 0; i < n; ++i) {
		if (bio[i]) ret.push_back(i);
	}
	return ret;
}

int hasEdge(int u, int v) {
    auto c1 = getConnected(u);
    auto c2 = getConnected(v);
    int empty = 0;
    for (auto a : c1) {
    	for (auto b : c2) {
    		empty += (adj[a][b] == 0);
    	}
    }
    if (empty == 1) {
    	adj[u][v] = 1;
    	adj[v][u] = 1;
    	return 1;
    } else {
    	adj[u][v] = 2;
    	adj[v][u] = 2;
    	return 0;
    }
}

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