제출 #1041139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041139		vanea	게임 (IOI14_game)	C++14	100 / 100	244 ms	21188 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;

const int mxN = 2e3+10;

int p[mxN], n, d[mxN][mxN];
set<int> comp;

int get(int x) {
    return p[x] < 0 ? x : p[x] = get(p[x]);
}

void uni(int x, int y) {
    x = get(x); y = get(y);
    if(p[x] > p[y]) swap(x, y);
    comp.erase(y);
    for(auto it : comp) {
        if(it == x) continue;
        d[it][x] = d[x][it] = d[x][it] + d[y][it];
    }
    p[x] += p[y];
    p[y] = x;
}

int hasEdge(int x, int y) {
    if(d[get(x)][get(y)] == 1) {
        uni(x, y);
        return 1;
    }
    --d[get(x)][get(y)];
    --d[get(y)][get(x)];
    return 0;
}

void initialize(int N) {
    n = N;
    for(int i = 0; i < n; i++) p[i] = -1;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            d[i][j] = d[j][i] = 1;
        }
        comp.insert(i);
    }
}

/*
int main()
{
    initialize(4);
    cout << hasEdge(0, 1) << hasEdge(3, 0) << hasEdge(1, 2) << hasEdge(0, 2);
    cout << hasEdge(3, 1) << hasEdge(2, 3);
}*/

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