제출 #1326852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326852		tkm_algorithms	게임 (IOI14_game)	C++20	100 / 100	229 ms	18776 KiB

game

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

using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int N = 1600;
int cnt[N][N], a[N], sz[N];
int nn;
int find(int x) {
	if (a[x] == x)return x;
	return a[x] = find(a[x]);
}

void unite(int x, int y) {
	x = find(x), y = find(y);
	//assert(x != y);
	a[x] = y, sz[y] += sz[x];
	rep(i, 0, nn)
		cnt[i][y] += cnt[i][x],
		cnt[y][i] += cnt[i][x];
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x,int y) {
    return x + rng() % (y - x + 1);
}

bool al[N][N];

void initialize(int n) {
	nn = n;
	rep(i, 0, n)a[i] = i, sz[i] = 1;
	for (int i = 0; i < n-1; i += 2)
		if (i+1 < n)unite(i, i+1), al[i][i+1] = 1;
	//cout << al[1][3] << nl;
}

int c = 0;

int hasEdge(int u, int v) {
	if (u>v)swap(u, v);
	if(al[u][v]) {
		//unite(u, v);
		//cout << sz[2]
		return 1;
	}
	
	int U = u, V = v;
	u = find(u), v = find(v);
	cnt[u][v] += 1, cnt[v][u] += 1;
	//if (U == 0 && V == 2) {
		//cout << sz[u]*sz[v] << nl;
		//cout << sz[1] << " " << sz[3] << nl;
	//}
	if (cnt[u][v] == sz[u]*sz[v]) {
		unite(u, v);
		return 1;
	}
	return 0;
}

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