Submission #961149

#	Time	Username	Problem	Language	Result	Execution time	Memory
961149		Nahian9696	Game (IOI14_game)	C++17	100 / 100	288 ms	31648 KiB

game

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


int n, num_comps;

int par[2000];

int comp_size[2000];
int comp_edges[2000][2000];

int find(int u) {
    if (par[u] == u) {
        return u;
    }
    return par[u] = find(par[u]);
}

void initialize(int nn) {
    n = nn;
    for (int i = 0; i < n; i++) {
        par[i] = i;
        comp_size[i] = 1;
        for(int j = 0; j < n; j++) {
            comp_edges[i][j] = 0;
        }
    }
    num_comps = n;
}

int hasEdge(int u, int v) {

    // if (find(u) == find(v)) {
    //     return 1;
    // }


    u = find(u);
    v = find(v);

    if(comp_edges[u][v] + 1 == comp_size[u] * comp_size[v]) {
        comp_edges[u][v] = 0;
        comp_edges[v][u] = 0;

        for(int i = 0; i < n; i++) {
            comp_edges[u][i] += comp_edges[v][i];
            comp_edges[v][i] = 0;
            comp_edges[i][u] += comp_edges[i][v];
            comp_edges[i][v] = 0;
        }

        comp_size[u] += comp_size[v];

        comp_size[v] = 0;

        par[v] = u;

        return 1;
    } else {
        comp_edges[u][v]++;
        comp_edges[v][u]++;
        return 0;
    }


    // if(num_comps > 2) {
    //     if(find(u) < find(v)) {
    //         std::swap(u, v);
    //     }
    //     par[find(u)] = find(v);
    //     num_comps--;
    //     return 1;
    // } else {
    //     return 0;
    // }


    return 1;
}

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