Submission #689413

#	Time	Username	Problem	Language	Result	Execution time	Memory
689413		sharaelong	Game (IOI14_game)	C++17	0 / 100	6 ms	9176 KiB

game

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

const int MAX_N = 1500 + 1;

int n;
int queried[MAX_N][MAX_N];
int par[MAX_N];
vector<int> group[MAX_N];
int remain_deg[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;
    if (group[u].size() > group[v].size()) swap(u, v);
    par[u] = v;
    for (int x: group[u]) group[v].push_back(x);
    remain_deg[v] = 0;
    for (int x: group[v]) {
        for (int i=0; i<n; ++i) {
            if (find(i) != v && queried[find(i)][x] != 0) {
                remain_deg[v]++;
            }
        }
    }
    // cout << u << ' ' << v << ' ' << remain_deg[v] << endl;
}

void initialize(int N) {
    n = N;
    memset(queried, -1, sizeof queried);
    iota(par, par+n, 0);
    for (int i=0; i<n; ++i) group[i].push_back(i);
    fill(remain_deg, remain_deg+n, n-1);
}

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

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