제출 #967264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
967264		VMaksimoski008	Game (IOI14_game)	C++14	15 / 100	4 ms	11096 KiB

game

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

struct DSU {
    int n, cnt[1505][1505];
    vector<int> par, size;

    DSU() {
        par.resize(1505);
        size.resize(1505, 1);
        for(int i=0; i<1505; i++) {
            par[i] = i;
            for(int j=0; j<1505; j++) cnt[i][j] = 0;
        }
    }

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

    bool uni(int a, int b) {
        a = find(a);
        b = find(b);

        if(a == b) return 0;
        if(cnt[a][b] + 1 < size[a] * size[b]) {
            cnt[a][b]++;
            cnt[b][a]++;
            return 0;
        }
        if(size[a] < size[b]) swap(a, b);

        size[a] += size[b];
        par[b] = a;

        for(int i=0; i<n; i++) {
            if(a == i) continue;
            cnt[a][i] += cnt[b][i] + cnt[i][b];
            cnt[i][a] += cnt[b][i] + cnt[i][b];
        }

        return 1;
    }
} dsu;

void initialize(int n) {

}

int hasEdge(int u, int v) {
    return dsu.uni(u, v);
}

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