제출 #368817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
368817		benedict0724	게임 (IOI14_game)	C++17	100 / 100	644 ms	25200 KiB

game

#include "game.h"
int cnt[1500][1500];
int link[1500], h[1500], m;

int _find(int x){
    if(x == link[x]) return x;
    return link[x] = _find(link[x]);
}
bool _unite(int x, int y){
    x = _find(x), y = _find(y);
    if(x == y) return 1;
    if(h[x] + h[y] == m) return 0;
    if(cnt[x][y] >= 2){
        cnt[x][y]--; cnt[y][x]--;
        return 0;
    }
    link[x] = y; h[y] += h[x];
    for(int i=0;i<m;i++){
        cnt[y][i] += cnt[x][i]; cnt[i][y] += cnt[i][x];
    }
    return 1;
}
void initialize(int n) {
    m = n;
    for(int i=0;i<n;i++){
        link[i] = i; h[i] = 1;
        for(int j=0;j<n;j++) cnt[i][j] = 1;
    }
}

int hasEdge(int u, int v) {
    return _unite(u, v);
}

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