Submission #1060234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060234		MrDogMeat	Game (IOI14_game)	C++17	100 / 100	237 ms	26704 KiB

game

#include<bits/stdc++.h>
#include "game.h"

using namespace std;

const int MAX_N = 1505;

int N;
int head[MAX_N], tail[MAX_N], nxt[MAX_N], Size[MAX_N];
int cnt[MAX_N][MAX_N];

void initialize(int n) {
    N = n;
    for(int i = 0; i < n; i++) {
        head[i] = tail[i] = i;
        nxt[i] = -1;
        Size[i] = 1;
        for(int j = 0; j < n; j++) {
            cnt[i][j] = 1;
        }
    }
}

void Union(int u, int v) {
    if(Size[u] > Size[v]) swap(u, v);

    for(int i = tail[u]; i > -1; i = nxt[i]) {
        head[i] = v;
    }
    nxt[u] = tail[v];
    tail[v] = tail[u];
    Size[v] += Size[u];

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

int hasEdge(int u, int v) {
    u = head[u], v = head[v];
    if(cnt[u][v] == 1) {
        Union(u, v);
        return 1;
    }
    cnt[u][v]--;
    cnt[v][u]--;
    return 0;
}

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