Submission #422133

#	Time	Username	Problem	Language	Result	Execution time	Memory
422133		daanolav	Game (IOI14_game)	C++14	0 / 100	13 ms	23760 KiB

game

#include "game.h"
#include <vector>

using namespace std;

#define MAXN 1000001

typedef vector<int> vi;

int n;

int ufParent[MAXN];
int ufSize[MAXN];
int ufLinkingPossibilities[MAXN];
vi ufPossibleConnections[MAXN];

int ufFind(int a) {
    if(ufParent[a] == a) {
        return a;
    }
    ufParent[a] = ufFind(ufParent[a]);
    return ufParent[a];
}

void ufUnite(int a, int b) {
    a = ufFind(a);
    b = ufFind(b);
    if(ufSize[a] > ufSize[b]) {
        swap(a,b);
    }


    ufParent[b] = a;
    ufSize[a] += ufSize[b];
    for(int i = 0; i < n; ++i) {
        if(i == a || i == b) {
            //ufLinkingPossibilities[a] -= ufPossibleConnections[a][i];
            ufPossibleConnections[a][i] = 0;
        } else {
            ufPossibleConnections[a][i] += ufPossibleConnections[b][i];
            //ufLinkingPossibilities[a] += ufPossibleConnections[b][i];

            ufPossibleConnections[i][a] += ufPossibleConnections[i][b];
            ufPossibleConnections[i][b] = 0;
        }
    }

}

void initialize(int n) {
    ::n = n;
    for(int i = 0; i < n; ++i) {
        ufParent[i] = i;
        ufSize[i] = 1;
        ufLinkingPossibilities[i] = 0;
        for(int j = 0; j < n; ++j) {
            if(i == j) {
                ufPossibleConnections[i].push_back(0);
                continue;
            }
            ufPossibleConnections[i].push_back(1);
            ufLinkingPossibilities[i] += 1;

        }
    }

}

int hasEdge(int u,int v) {
    if(ufPossibleConnections[ufFind(u)][ufFind(v)] > 1) {
        return 0;
    } else {
        ufUnite(u,v);
        return 1;
    }
}

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