제출 #370324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
370324		mjhmjh1104	게임 (IOI14_game)	C++17	100 / 100	469 ms	16096 KiB

game

#include "game.h"
#include <tuple>
#include <algorithm>
using namespace std;

int uf[1506], cnt[1506][1506], n;
int k;

int _find(int x) {
    if (uf[x] == -1) return x;
    return uf[x] = _find(uf[x]);
}

void initialize(int N) {
    n = N, k = 0;
    for (int i = 0; i < n; i++) {
        uf[i] = -1;
        for (int j = i + 1; j < n; j++) cnt[i][j] = 1;
    }
}


int hasEdge(int u, int v) {
    k++;
    if (k == n * (n - 1) / 2) return 0;
    u = _find(u), v = _find(v);
    if (u == v) return 0;
    tie(u, v) = make_pair(min(u, v), max(u, v));
    if (cnt[u][v] > 1) return cnt[u][v]--, 0;
    for (int i = 0; i < n; i++) if (_find(i) == i && _find(i) != u && _find(i) != v) {
        auto [ a, b ] = make_pair(min(u, i), max(u, i));
        auto [ c, d ] = make_pair(min(v, i), max(v, i));
        cnt[a][b] += cnt[c][d];
    }
    uf[v] = u;
    return 1;
}

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