Submission #674824

#	Time	Username	Problem	Language	Result	Execution time	Memory
674824		bashkort	Game (IOI14_game)	C++17	100 / 100	349 ms	25180 KiB

game

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

using namespace std;

constexpr int N = 1500;

int p[N], e[N][N], n;

int leader(int x) {
    while (x != p[x]) x = p[x] = p[p[x]];
    return x;
}

bool unite(int x, int y) {
    x = leader(x), y = leader(y);
    if (x == y || e[x][y] > 1) {
        if (x != y) {
            e[x][y] -= 1;
            e[y][x] -= 1;
        }
        return false;
    }
    p[y] = x;
    for (int to = 0; to < n; ++to) {
        if (to != x) {
            e[x][to] += e[y][to];
            e[to][x] += e[to][y];
        }
    }
    return true;
}

void initialize(int n) {
    ::n = n;
    iota(p, p + n, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            e[i][j] = e[j][i] = 1;
        }
    }
}

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

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