Submission #385420

#	Time	Username	Problem	Language	Result	Execution time	Memory
385420		Keshi	Game (IOI14_game)	C++17	100 / 100	540 ms	17260 KiB

game

//In the name of God
#include <bits/stdc++.h>
#include "game.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 1600;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

int n, sz[maxn], dsu[maxn], g[maxn][maxn];

void initialize(int n_) {
	n = n_;
	for(ll i = 0; i < n; i++){
		sz[i] = 1;
		dsu[i] = i;
	}
}

int hasEdge(int u, int v){
	u = dsu[u];
	v = dsu[v];
	g[v][u]++;
	g[u][v]++;
	if(g[v][u] == sz[v] * sz[u]){
		for(ll i = 0; i < n; i++){
			if(dsu[i] == u){
				dsu[i] = v;
				sz[v]++;
			}
			else if(dsu[i] == i){
				g[i][v] += g[i][u];
				g[v][i] += g[u][i];
			}
		}
		return 1;
	}
    return 0;
}

/*int main(){
	freopen("sample-1.in", "r", stdin);

	int n_;
	cin >> n_;
	initialize(n_);
	for(ll i = 0; i < n_ * (n_ - 1) / 2; i++){
		int v, u;
		cin >> v >> u;
		cout << v << " " << u << " -> " << hasEdge(v, u) << "\n";
	}

    return 0;
}*/

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