Submission #623197

#	Time	Username	Problem	Language	Result	Execution time	Memory
623197		prvocislo	Game (IOI14_game)	C++17	100 / 100	396 ms	25200 KiB

game

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

int n;
vector<vector<int> > a;
struct dsu
{
	vector<int> p;
	int root(int u)
	{
		return u == p[u] ? u : p[u] = root(p[u]);
	}
	bool merge(int u, int v)
	{
		u = root(u), v = root(v);
		if (u == v) return false;
		p[v] = u;
		for (int i = 0; i < n; i++)
		{
			a[u][i] += a[v][i];
			a[v][i] = 0;
			a[i][u] += a[i][v]; //i love you
			a[i][v] = 0;
		}
		return true;
	}
	void init(int n)
	{
		p.assign(n, 0);
		for (int i = 0; i < n; i++) p[i] = i;
	}
};
dsu d;
void initialize(int N)
{
	n = N;
	a.assign(n, vector<int>(n, 1));
	d.init(n);
}
int hasEdge(int u, int v)
{
	u = d.root(u);
	v = d.root(v);
	if (a[u][v] == 1)
	{
		d.merge(u, v);
		return 1;
	}
	else
	{
		a[u][v]--;
		a[v][u]--;
		return 0;
	}
}

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