Submission #250537

#	Time	Username	Problem	Language	Result	Execution time	Memory
250537		tictaccat	Game (IOI14_game)	C++14	100 / 100	532 ms	18004 KiB

game

#include <bits/stdc++.h>

using namespace std;

vector<int> p, sz;
vector<vector<int>> adj;
int n;

int findSet(int u) {
    return (p[u] == u ? u : p[u] = findSet(p[u]));
}

bool same(int u, int v) {
    return findSet(u) == findSet(v);
}

void unite(int u, int v) {
    if (sz[u] < sz[v]) swap(u,v);
    for (int i = 0; i < n; i++) {
        adj[u][i] += adj[v][i];
        adj[i][u] = adj[u][i];
    }
    p[v] = u;
    sz[u] += sz[v];
}

void initialize(int n) {
    ::n = n;
    p.resize(n);
    for (int i = 0; i < n; i++) p[i] = i;
    sz.resize(n,1);
    adj.resize(n, vector<int>(n,0));
}

int hasEdge(int u, int v) {
//    cout << u << " " << v << " " << same(u,v) << "\n";
    u = findSet(u);
    v = findSet(v);
    if (u == v) return false;
    if (adj[u][v] + 1 == sz[u]*sz[v]) {
        unite(u,v);
        return true;
    }
    adj[u][v]++;
    adj[v][u]++;
    return false;
}

// int main() {

//     initialize(5);

//     cout << hasEdge(0,1) << "\n";
//     cout << hasEdge(2,3) << "\n";

//     cout << hasEdge(0,2) << "\n";
//     cout << hasEdge(0,3) << "\n";
//     cout << hasEdge(1,2) << "\n";
//     cout << hasEdge(1,3) << "\n";


// }

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