제출 #1218247

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218247		Hamed_Ghaffari	게임 (IOI14_game)	C++20	100 / 100	215 ms	21880 KiB

game

#include <bits/stdc++.h>
using namespace std;

const int MXN = 3003;

int n, dsu[MXN], cnt[MXN][MXN], tmp[MXN];

void initialize(int n) {
    ::n = n;
    iota(dsu, dsu+n, 0);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cnt[i][j] = i!=j;
}

void merge(int u, int v) {
    for(int i=0; i<n; i++)
        dsu[i] = dsu[i]==v ? u : dsu[i],
        tmp[i] = cnt[u][i] + cnt[v][i];
    for(int i=0; i<n; i++)
        cnt[u][i] = cnt[i][u] = tmp[i];
}

int hasEdge(int u, int v) {
    cnt[dsu[u]][dsu[v]]--;
    cnt[dsu[v]][dsu[u]]--;
    if(!cnt[dsu[u]][dsu[v]]) {
        merge(dsu[u], dsu[v]);
        return 1;
    }
    return 0;
}

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