Submission #577589

#	Time	Username	Problem	Language	Result	Execution time	Memory
577589		Mazaalai	Game (IOI14_game)	C++17	42 / 100	1097 ms	7268 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define lb lower_bound
#define LINE "------------\n"
using namespace std;
using PII = pair <int, int>;
const int N = 1500;
// bool path[N][N];
set <PII> edges;
int n;
void initialize(int _n) {
    n = _n;
    for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++) {
        edges.insert({i, j});
    }
}
int par[N];
int find(int a) {
    return par[a] = (par[a] == a ? a : find(par[a]));
}
bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return 0;
    par[b] = a;
    return 1;
}
int hasEdge(int u, int v) {
    if (u > v) swap(u, v);
    edges.erase({u, v});
    int disjoint = n;
    iota(par, par+n, 0);
    for (auto [a, b] : edges) {
        if (disjoint == 1) break;
        // cout << a << " " << b << " "
        disjoint -= merge(a, b);
    }
    if (disjoint != 1) edges.insert({u, v});
    return disjoint != 1;
}

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