Submission #159311

#	Time	Username	Problem	Language	Result	Execution time	Memory
159311		TAISA_	Game (IOI14_game)	C++14	100 / 100	517 ms	16540 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int co[1500][1500];
struct UF {
    vector<vector<int>> vs;
    vector<int> par;
    int n;
    void build(int n_) {
        n = n_;
        vs.resize(n);
        par.resize(n);
        for (int i = 0; i < n; i++) {
            vs[i].push_back(i);
            par[i] = i;
        }
    }
    bool unite(int u, int v) {
        if (par[u] == par[v]) {
            return false;
        }
        int tu = u, tv = v;
        u = par[tu];
        v = par[tv];
        int su = vs[u].size(), sv = vs[v].size();
        if (su < sv) {
            swap(u, v);
            swap(su, sv);
            swap(tu, tv);
        }
        co[u][v]++;
        co[v][u]++;
        if (co[u][v] == su * sv) {
            for (auto &e : vs[v]) {
                vs[u].push_back(e);
                par[e] = u;
            }
            for (int i = 0; i < n; i++) {
                co[u][i] += co[v][i];
                co[i][u] += co[i][v];
            }
            return true;
        }
        return false;
    }
};
UF uf;
void initialize(int n) { uf.build(n); }
int hasEdge(int u, int v) {
    if (uf.unite(u, v)) {
        return 1;
    } else {
        return 0;
    }
}

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