Submission #381673

#	Time	Username	Problem	Language	Result	Execution time	Memory
381673		Aryan_Raina	Game (IOI14_game)	C++14	42 / 100	1085 ms	1264 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;

struct UFDS {
    int n, cc;
    vector<int> len, par;
    void init(int x) {
        n = cc = x;
        par.resize(n+2);
        len.assign(n+2, 1);
        iota(par.begin(), par.end(), 0);
    }
    int fin(int v) { return par[v] == v ? v : par[v] = fin(par[v]); }
    bool join(int a, int b) {
        a = fin(a); b = fin(b);
        if(a == b) return false;
        if(len[a] < len[b])
            swap(a, b);
        par[b] = a;
        len[a]+=len[b];
        cc--;
        return true;
    }
};

int n; bool adj[1505][1501];
void initialize(int _n) {
	n = _n; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) adj[i][j] = adj[j][i] = 1;
	}
}

int hasEdge(int u, int v) {
	if (u < v) swap(u, v);
	UFDS ufds; ufds.init(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) if (!(i == u && j == v) && adj[i][j]) {
			ufds.join(i, j);
		}
	}
	if (ufds.cc == 1) {
		adj[u][v] = adj[v][u] = 0;
		return 0;
	} else {
		return 1;
	}
}

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