제출 #286951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286951		Marte	게임 (IOI14_game)	C++17	0 / 100	1 ms	512 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1500;
int parents[N];
set<pair<int, int>> links[N];

int find(int v) {
    if (v == parents[v])
        return v;
    return parents[v] = find(parents[v]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b)
        parents[b] = a;
}

void initialize(int n) {
    for (int i = 0; i < n; ++i) {
        parents[i] = i;
        for (int j = 0; j < n; ++j) {
            if (i != j)
                links[i].emplace(i, j);
        }
    }
}

int hasEdge(int u, int v) {
    int c1 = find(u);
    int c2 = find(v);
    int c3 = -1;
    if (c1 == c2)
        return 1;
    links[c1].erase({u, v});
    if (links[c1].size() == 1) {
        int self, other;
        tie(self, other) = *links[c1].begin();
        c3 = find(other);
        merge(c1, c3);
        links[c3].erase({other, self});
        links[c1] = move(links[c3]);
    }
    if (c2 == c3)
        return 0;
    links[c2].erase({v, u});
    if (links[c2].size() == 1) {
        int self, other;
        tie(self, other) = *links[c2].begin();
        c3 = find(other);
        merge(c2, c3);
        links[c3].erase({other, self});
        links[c2] = move(links[c3]);
    }
    return 0;
}

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