Submission #585561

#	Time	Username	Problem	Language	Result	Execution time	Memory
585561		LastRonin	Game (IOI14_game)	C++14	100 / 100	388 ms	18676 KiB

game

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

using namespace std;

const int N = 1610;

int gn;
int p[N], sz[N];
bool was[N][N];

int get(int a) {
	return (p[a] = (p[a] == a ? a : get(p[a])));
}

void unt(ll a, ll b) {
	a = get(a);
	b = get(b);
	if(a == b)return;
	if(sz[a] < sz[b])swap(a, b);
	p[b] = a;
	sz[a] += sz[b];
}


void initialize(int n) {
	gn = n;
	for(int i = 0; i < n; i++)
		sz[i] = 1, p[i] = i;
}

int hasEdge(int u, int v) {
	was[u][v] = 1;
	was[v][u] = 1;
    if(get(u) == 0 && get(v) == 0)return 0;
    if(get(u) != 0 && get(v) != 0)return 0;
    if(get(u) != 0)swap(u, v);
    if(get(u) == 0) { 
		for(int i = 0; i < gn; i++) {
			if(get(i) == 0 && !was[i][v])return 0;
 		}
 		unt(u, v);
 		return 1;
 	}
    return 1;
}
/*
int read_int() {
    int x;
    assert(scanf("%d", &x) == 1);
    return x;
}

int main() {
    int n, u, v;
    n = read_int();
    initialize(n);
    for (int i = 0; i < n * (n - 1) / 2; i++) {
        u = read_int();
        v = read_int();
        printf("%d\n", hasEdge(u, v));
    }
    return 0;
}
*/

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