Submission #159283

#	Time	Username	Problem	Language	Result	Execution time	Memory
159283		oolimry	Game (IOI14_game)	C++14	100 / 100	515 ms	17016 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;
typedef pair<int,int> ii;
static int m[5000000];
int N;
int mii(int x, int y){
	if(x > y) swap(x,y);
	return x * 2000 + y;
}
void initialize(int n) {
	uf.create(n);
	N = n;
	for(int i = 0;i < n;i++){
		for(int j = i+1;j < n;j++){
			m[mii(i,j)] = 1;
		}
	}
}


int hasEdge(int u, int v) {
	if(uf.isSameSet(u,v)){
		return 0;
	}
    int x = uf.findSet(u);
    int y = uf.findSet(v);
    
    
    if(m[mii(x,y)] == 1){
		uf.unionSet(u,v);
		
		for(int i = 0;i < N;i++){
			int w = i;
			int z = uf.findSet(u);
			
			m[mii(w,z)] = m[mii(w,x)] + m[mii(w,y)];
			
		}
		
		
		return 1;
	}
	else{
		m[mii(x,y)]--;
		return 0;
	}
}

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