제출 #416141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416141		dxz05	Game (IOI14_game)	C++14	0 / 100	1 ms	284 KiB

game

#include "game.h"

const int MAXN = 111111;

int p[MAXN], sz[MAXN], deg[MAXN], ask_count[MAXN];
int find(int x){
    return (x == p[x] ? x : p[x] = find(p[x]));
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return;
    p[x] = y;
    sz[y] += sz[x];
}

int n;
void initialize(int _n) {
    n = _n;
    for (int i = 0; i < n; i++) p[i] = i, sz[i] = 1;
}

int hasEdge(int u, int v) {
    ask_count[u]++;
    ask_count[v]++;
    if (find(u) == find(v)) return 0;
    if (sz[p[u]] + sz[p[v]] == n) return 0;
    if (ask_count[u] == n - 1 && deg[u] == n - 2) return 0;
    if (ask_count[v] == n - 1 && deg[v] == n - 2) return 0;
    if (deg[u] < 2 && deg[v] < 2){
        unite(u, v);
        deg[u]++;
        deg[v]++;
        return 1;
    }
    return 0;
}

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