Submission #1089009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089009		Alihan_8	Game (IOI14_game)	C++17	100 / 100	219 ms	26708 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 1505;

int cnt[N][N];

struct dsu{
	int fa[N];
	
	vector <vector<int>> c;
	
	dsu(){
		c.resize(N);
		
		for ( int i = 0; i < N; i++ ){
			fa[i] = i;
			c[i].push_back(i);
		}
	}
	
	int get(int u){
		return fa[u] ^ u ? fa[u] = get(fa[u]) : u;
	}
	
	int merge(int u, int v){
		u = get(u), v = get(v);
		
		cnt[u][v]++, cnt[v][u]++;
		
		//~ assert(u != v);
		
		if ( c[u].size() < c[v].size() ) swap(u, v);
		
		int x = c[u].size() * c[v].size();
		
		if ( cnt[u][v] == x ){
			for ( int j = 0; j < N; j++ ){
				cnt[u][j] += cnt[v][j];
				cnt[j][u] += cnt[v][j];
			}
			
			for ( auto &y: c[v] ){
				c[u].push_back(y);
				fa[y] = u;
			} c[v].clear();
			
			return 1;
		}
		
		return 0;
	}
} ds;

void initialize(int N) {
	
}

int hasEdge(int u, int v) {
	return ds.merge(u, v);
}

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