제출 #592727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592727		shrimb	게임 (IOI14_game)	C++17	42 / 100	1076 ms	2924 KiB

game

#include "game.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1501;

int dsu[maxn];
int tmp[maxn];

int adj[maxn][maxn];

int N;

int Find (int i) {
    return dsu[i] == i ? i : dsu[i] = Find(dsu[i]);
}

void Union (int i, int j) {
    dsu[Find(i)] = Find(j);
}

void initialize(int n) {
    N = n;
    for (int i = 0 ; i < n ; i++) {
        dsu[i] = i;
        for (int j = i + 1 ; j < n ; j++) adj[i][j] = 0;
    }
}

int hasEdge(int u, int v) { // u < v
    if (v < u) swap(u, v);
    adj[u][v] = 1;
    if (Find(u) == Find(v)) {
        return 0;
    }
    int ret = 0;
    copy(dsu, dsu + N, tmp);
    for (int i = 0 ; i < N ; i++) {
        for (int j = i + 1 ; j < N ; j++) {
            if (!adj[i][j] and Find(i) != Find(j)) Union(i, j);
        }
    }
    int rut = Find(0);
    for (int i = 1 ; i < N ; i++) if (rut != Find(i)) ret = 1;
    copy(tmp, tmp + N, dsu);
    if (ret) Union(u, v);
    return ret;
}

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