Submission #1131288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131288		mingga	Game (IOI14_game)	C++20	100 / 100	307 ms	15876 KiB

game

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
// #define int long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 1505;
int cnt[N][N];

struct DSU {
    int n;
    vector<int> par, sz;
    DSU() {}
    DSU(int n) : n(n) {
        par.resize(n + 1, 0);
        sz.resize(n + 1, 1);
        for(int i = 1; i <= n; i++) par[i] = i;
    }
    int find(int u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }
    void join(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return ;
        if(sz[u] < sz[v]) {
            swap(u, v);
        }
        sz[u] += sz[v];
        par[v] = u;
        for(int i = 1; i <= n; i++) cnt[u][i] += cnt[v][i], cnt[i][u] += cnt[i][v];
    }
    bool is_joined(int u, int v) {
        return find(u) == find(v);
    }
} dsu;

void initialize(int n) {
    dsu = DSU(n);
}

int hasEdge(int x, int y) {
    x++, y++;
    int x1 = dsu.find(x);
    int y1 = dsu.find(y);
    if(x1 == y1) return 1;
    if(dsu.sz[x1] * dsu.sz[y1] == cnt[x1][y1] + 1) {
        dsu.join(x1, y1);
        cnt[x1][y1]++;
        cnt[y1][x1]++;
        return 1;
    } else {
        cnt[x1][y1]++;
        cnt[y1][x1]++;
        return 0;
    }
}

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