Submission #1278598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278598		monval	Game (IOI14_game)	C++20	100 / 100	251 ms	22140 KiB

game

#include "game.h"

int N;
int* components;
int** component_sets;
int* component_sizes;
int** component_pair_connections;

void initialize(int n){
    N = n;
    components = new int[N];
    component_sets = new int*[N];
    component_sizes = new int[N];
    component_pair_connections = new int*[N];
    for(int i = 0; i < N; i++){
        component_sets[i] = new int[N];
        component_pair_connections[i] = new int[N];
        components[i] = i;
        component_sets[i][0] = i;
        component_sizes[i] = 1;
        for(int j = 0; j < N; j++){
            component_pair_connections[i][j] = 0;
        }
    }
}

int hasEdge(int u, int v){
    int component_u = components[u];
    int component_v = components[v];
    int u_size = component_sizes[component_u];
    int v_size = component_sizes[component_v];
    if(component_pair_connections[component_u][component_v] == u_size * v_size - 1){
        component_sizes[component_u] += v_size;
        for(int i = 0; i < v_size; i++){
            component_sets[component_u][i + u_size] = component_sets[component_v][i];
            components[component_sets[component_v][i]] = component_u;
        }
        for(int i = 0; i < N; i++){
            component_pair_connections[component_u][i] += component_pair_connections[component_v][i];
            component_pair_connections[i][component_u] = component_pair_connections[component_u][i];
        }
        return 1;
    }else{
        component_pair_connections[component_u][component_v]++;
        component_pair_connections[component_v][component_u]++;
        return 0;
    }
}

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