Submission #1264597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264597		ortsac	게임 (IOI14_game)	C++20	100 / 100	224 ms	15956 KiB

game

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

using namespace std;

const int MAXN = 1505;

int n;
int qtd[MAXN][MAXN];
int dad[MAXN];
int sz[MAXN];

void initialize(int N) {
    n = N;
    memset(qtd, 0, sizeof qtd);
    for (int i = 0; i < n; i++) sz[i] = 1;
    for (int i = 0; i < n; i++) dad[i] = i;
}

int find(int x) {
    if (dad[x] == x) return x;
    return (dad[x] = find(dad[x]));
}

int hasEdge(int a, int b) {
    a = find(a), b = find(b);
    assert(a != b);
    if (sz[a] < sz[b]) swap(a, b); // b goes inside a, a is bigger
    if (qtd[a][b] != (sz[a]*sz[b] - 1)) {
        qtd[a][b]++;
        qtd[b][a]++;
        return 0;
    }
    dad[b] = a;
    sz[a] += sz[b];
    for (int i = 0; i < n; i++) {
        if (i == a) continue;
        qtd[i][a] += qtd[i][b];
        qtd[a][i] += qtd[b][i];
    }
    return 1;
}

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