Submission #813711

#	Time	Username	Problem	Language	Result	Execution time	Memory
813711		Pikachu	Game (IOI14_game)	C++17	42 / 100	1080 ms	1492 KiB

game

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

using namespace std;

const int maxn = 1510, maxm = maxn * (maxn - 1) / 2;
int n, m;
pair<int,int> edge[maxm];
bool remain[maxm];

int par[maxn];

int findpar(int x)
{
    return par[x] != -1 ? par[x] = findpar(par[x]) : x;
}

bool unite(int u, int v)
{
    u = findpar(u);
    v = findpar(v);
    if (u != v) return par[u] = v, true;
    return false;
}

bool check()
{
    memset(par, -1, sizeof par);
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (remain[i]) cnt += unite(edge[i].first, edge[i].second);
    }
    return cnt == n - 1;
}

void initialize(int n) 
{
    ::n = n;
    m = n * (n - 1) / 2;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            edge[cnt++] = {i, j};
        }
    }
    for (int i = 0; i < m; i++) remain[i] = true;
}

int cnt = 0;

int hasEdge(int u, int v) 
{
    if (u > v) swap(u, v);
    int id = lower_bound(edge, edge + m, make_pair(u, v)) - edge;
    remain[id] = false;
    if (check()) return 0;
    remain[id] = true;
    return 1;
}

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