Submission #539174

#	Time	Username	Problem	Language	Result	Execution time	Memory
539174		astoria	Game (IOI14_game)	C++14	100 / 100	522 ms	25156 KiB

game

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

int _n;
int allSets[1500][1500]; //<index,#ofthem>
int rankOfRoot[1500];
int parent[1500];

int root(int x) {
    if (parent[x]==-1) return x;
    return parent[x] = root(parent[x]);
}

void connect(int x, int y) {
    int rootX = root(x), rootY = root(y);
    if (rootX == rootY) return; // same root
    if (rankOfRoot[rootX] > rankOfRoot[rootY]) {
        parent[rootY] = rootX;
    } else if (rankOfRoot[rootX] < rankOfRoot[rootY] ){
        parent[rootX] = rootY;
    } else {
        parent[rootY] = rootX;
        rankOfRoot[rootX]++;
    }
}

bool isConnected(int x, int y) {
    return root(x) == root(y);
}

void initialize (int n){
    _n = n;
    memset(parent,-1,sizeof(parent));
    memset(rankOfRoot,1,sizeof(rankOfRoot));
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (i==j) allSets[i][j] = 0;
            else allSets[i][j] = 1;
        }
    }
}

int hasEdge(int u, int v){
    int x = root(u); int y = root(v);
    /*if (u==0 && v==2){
      cout << "R" << x << " " << y << endl;
      cout << allSets[0][2] << endl;
    }*/
    allSets[x][y]--;
    allSets[y][x]--;
    if (allSets[x][y] <= 0){
        //connect
        connect(x,y);
        int z = root(y);
        if (z==y){
            for (int i=0; i<_n; i++){
                if (i==x) continue;
                if (i==y) continue;
                if (allSets[i][x] <= 0) continue;
                int res = allSets[i][x];
                allSets[i][x] = 0;
                allSets[x][i] = 0;
                allSets[i][y] += res;
                allSets[y][i] += res;
            }
        }
        if (z==x){
            for (int i=0; i<_n; i++){
                if (i==x) continue;
                if (i==y) continue;
                if (allSets[i][y] <= 0) continue;
                int res = allSets[i][y];
                allSets[i][y] = 0;
                allSets[y][i] = 0;
                allSets[i][x] += res;
                allSets[x][i] += res;
            }
        }
        return 1;
    }
    else{
        return 0;
    }
}

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