Submission #159305

#	Time	Username	Problem	Language	Result	Execution time	Memory
159305		TAISA_	Game (IOI14_game)	C++14	42 / 100	1093 ms	4920 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int vis[1500][1500];
struct UF {
    vector<vector<int>> vs;
    vector<int> par;
    void build(int 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]) {
            vis[u][v] = 1;
            vis[v][u] = 1;
            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);
        }
        int co = 0;
        for (int i = 0; i < su; i++) {
            for (int j = 0; j < sv; j++) {
                if (vis[vs[u][i]][vs[v][j]]) {
                    co++;
                }
            }
        }
        vis[tu][tv] = 1;
        vis[tv][tu] = 1;
        if (co + 1 == su * sv) {
            for (auto e : vs[v]) {
                vs[u].push_back(e);
                par[e] = u;
            }
            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: 0 / 58