Submission #576663

#	Time	Username	Problem	Language	Result	Execution time	Memory
576663		elazarkoren	Game (IOI14_game)	C++17	100 / 100	473 ms	20916 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#pragma GCC target("popcnt")
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;


struct Dsu {
    int n;
    vi par, sz;
    vvi cnt;
    Dsu() {}
    Dsu(int n): n(n) {
        par.resize(n), sz.resize(n, 1);
        iota(all(par), 0);
        cnt.resize(n, vi(n, 1));
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    bool Union(int a, int b) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) return false;
        if (sz[pa] < sz[pb]) swap(pa, pb);
        par[pb] = pa;
        sz[pa] += sz[pb];
        for (int i = 0; i < n; i++) {
            cnt[pa][i] += cnt[pb][i];
            cnt[i][pa] += cnt[i][pb];
        }
        return true;
    }
};

const int MAX_N = 1505;

int n;
Dsu dsu;

void initialize(int N) {
    n = N;
    dsu = Dsu(n);
}

int hasEdge(int u, int v) {
    int a = dsu.Find(u), b = dsu.Find(v);
    if (dsu.cnt[a][b] > 1) {
        dsu.cnt[a][b]--, dsu.cnt[b][a]--;
        return 0;
    }
    dsu.Union(u, v);
    return 1;
}

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