Submission #971252

#	Time	Username	Problem	Language	Result	Execution time	Memory
971252		PenguinsAreCute	Game (IOI14_game)	C++17	100 / 100	309 ms	26536 KiB

game

// this is literally a 24-liner
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int cnt[1505][1505], par[1505], sz[1505];
int ufds(int x) {return par[x]=(par[x]==x?x:ufds(par[x]));}
void add(int u, int v) {
	u = ufds(u), v = ufds(v);
	if(sz[u]>sz[v]) swap(u,v);
	sz[v] += sz[u];
	par[u] = v;
	for(int i=0;i<1505;i++) cnt[v][i]=(cnt[i][v]+=cnt[i][u]);
}
void initialize(int n) {
	iota(par,par+1505,0);
	fill(sz,sz+1505,1);
}
int hasEdge(int u, int v) {
	u = ufds(u); v = ufds(v);
	if(u==v) return 0;
	cnt[u][v]++; cnt[v][u]++;
	if(cnt[u][v]==sz[u]*sz[v]) {add(u,v); return 1;}
	else return 0;
}

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