Submission #489337

#	Time	Username	Problem	Language	Result	Execution time	Memory
489337		Drew_	Game (IOI14_game)	C++17	100 / 100	377 ms	19712 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define ii pair<int, int>

constexpr int MAX = 1569;

int n;
int ds[MAX];
int ctr[MAX][MAX];

inline int frep(int x) { return ds[x] == x ? x : ds[x] = frep(ds[x]); }
inline void join(int x, int y)
{
	x = frep(x); y = frep(y);
	if (x == y)
		return;

	for (int i = 0; i < n; ++i)
	{
		if (i == x || i == y)
			continue;

		ctr[i][x] += ctr[i][y];
		ctr[x][i] += ctr[y][i];
	}
	ds[y] = x;
}

void initialize(int N) {
	n = N;

	for (int i = 0; i < n; ++i)
		ds[i] = i;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			ctr[i][j] = 1;
}


int hasEdge(int u, int v) {
	u = frep(u); v = frep(v);

	if (ctr[u][v] > 1)
	{
		ctr[u][v]--; ctr[v][u]--;
		return 0;
	}

	join(u, v);
	return 1;
}

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