Submission #1129005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129005		djs100201	Game (IOI14_game)	C++20	100 / 100	498 ms	24508 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define all(v) v.begin(), v.end()
using namespace std;
using ll = int;
const ll n_ = 2e3 + 100;
ll checked[n_], con[n_][n_], N, par[n_];
vector<ll> v[n_];
ll find(ll x) {
    if (par[x] < 0) return x;
    return par[x] = find(par[x]);
}
void merge(ll x, ll y) {
    x = find(x), y = find(y);
    if (v[x].size() < v[y].size()) swap(x, y);
    for (auto nxt : v[y]) v[x].push_back(nxt);
    v[y].clear();
    par[y] = x;
}
void initialize(int n) {
    N = n;
    memset(con, -1, sizeof(con));
    memset(par, -1, sizeof(par));
    for (int i = 1; i <= n; i++) {
        v[i].clear();
        v[i].push_back(i);
    }
}
bool go(ll x, ll y) {
    ll cnt = 0;
    x = find(x), y = find(y);
    for (auto i : v[x])
        for (auto j : v[y]) {
            if (con[i][j] == -1) cnt++;
            if (con[j][i] == -1) cnt++;
            if (cnt > 3) return false;
        }
    return cnt == 2;
}
int hasEdge(int u, int v) {
    u++, v++;
    if (go(u, v)) {
        con[u][v] = con[v][u] = 1;
        merge(u, v);
    }
    else con[u][v] = con[v][u] = 0;
    return con[u][v];
}

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