Submission #691977

#	Time	Username	Problem	Language	Result	Execution time	Memory
691977		sharaelong	Game (IOI14_game)	C++17	100 / 100	401 ms	25208 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1500 + 1;

int n;
int deg_remain[MAX_N][MAX_N];
int par[MAX_N];

int find(int x) {
    return par[x] = (x == par[x] ? x : find(par[x]));
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    par[u] = v;
    for (int i=0; i<n; ++i) {
        if (i == find(i) && i != u && i != v) {
            deg_remain[v][i] += deg_remain[u][i];
            deg_remain[i][v] = deg_remain[v][i];
        }
    }
}

void initialize(int N) {
    n = N;
    iota(par, par+n, 0);
    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            if (i != j) deg_remain[i][j] = 1;
        }
    }
}

int hasEdge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) {
        return 1;
    } else {
        if (deg_remain[u][v] == 1) {
            merge(u, v);
            return 1;
        } else {
            deg_remain[u][v]--;
            deg_remain[v][u]--;
            return 0;
        }
    }
}

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