Submission #159281

#	Time	Username	Problem	Language	Result	Execution time	Memory
159281		oolimry	Game (IOI14_game)	C++14	0 / 100	2 ms	380 KiB

game

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

using namespace std;

class UFDS {
typedef vector<int> vi;
public:
    vi p, rak, setSize;
    int numSets;

    void create(int n){
        setSize.assign(n, 1);
        numSets = n;
        rak.assign(n, 0);
        p.assign(n, 0);
        for(int i =0;i < n;i++){
            p[i] = i;
        }
    }

    int findSet(int i){
        return (p[i] == i) ? i : (p[i] = findSet(p[i]));
    }

    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }

    void unionSet(int i, int j){
        if(isSameSet(i,j))
            return;
        numSets--;
        int x = findSet(i);
        int y = findSet(j);

        if(rak[x] > rak[y]) {
            p[y] = x; setSize[x] += setSize[y];
        }

        else {
            p[x] = y; setSize[y] += setSize[x];
            if(rak[x] == rak[y]) rak[y]++;
        }

    }
};
UFDS uf;
void initialize(int n) {
	uf.create(n);
}

int hasEdge(int u, int v) {
    if(uf.isSameSet(u,v)) return 0;
    if(uf.numSets != 2){
		uf.unionSet(u,v);
		return 1;
	}
	else{
		return 0;
	}
}

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