Submission #422138

#	Time	Username	Problem	Language	Result	Execution time	Memory
422138		bipartite_matching	Game (IOI14_game)	C++14	100 / 100	372 ms	7824 KiB

game

#include <bits/stdc++.h>

#define forint(i, N) for (int i = 0; i < (N); i++)

using namespace std;

int n;

vector< vector<bool> > asked;
vector<bool> added;

vector<int> comp;

void initialize(int N) {
	n = N;

	asked.resize(n);
	for (auto& i : asked) {
		i.resize(n);
		fill(i.begin(), i.end(), false);
	}

	added.resize(n);
	fill(added.begin(), added.end(), false);
}

int hasEdge(int u, int v) {
	asked[u][v] = true;
	asked[v][u] = true;

	if (comp.size() == 0) {
		
		comp = {u, v};
		added[u] = true;
		added[v] = true;
	}

	if (!added[u] && !added[v]) {
		return 0;
	}
	if (added[u] && added[v]) {
		return 1;
	}
	

	if (added[u]) {
		for (auto& i : comp) {
			if (!asked[i][v] && i != u) {
				return 0;
			}
		}
		added[v] = true;
		comp.push_back(v);
		return 1;
	}
	if (added[v]) {
		for (auto& i : comp) {
			if (!asked[i][u] && i != v) {
				return 0;
			}
		}
		added[u] = true;
		comp.push_back(u);
		return 1;	
	}
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

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