Submission #935757

#	Time	Username	Problem	Language	Result	Execution time	Memory
935757		peterandvoi	Game (IOI14_game)	C++17	42 / 100	1031 ms	808 KiB

game

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

vector<vector<bool>> dd, used;

int cc;

struct dsu {
    int n;
    vector<int> e;

    dsu() {};

    dsu(int n): n(n) {
        e.resize(n, -1);
    }

    int get(int u) {
        return e[u] < 0 ? u : e[u] = get(e[u]);
    }

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

    void unite(int u, int v) {
         u = get(u);
         v = get(v);
         if (u != v) {
             if (e[u] > e[v]) {
                swap(u, v);
             }
             e[u] += e[v];
             e[v] = u;
         }
    }

    void reset() {
        fill(e.begin(), e.end(), -1);
    }
} G;

int hasEdge(int u, int v) {
    if (u > v) {
        swap(u, v);
    }
    G.reset();
    int n = G.n;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (i != u || j != v) {
                if (dd[i][j]) {
                    if (used[i][j]) {
                        G.unite(i, j);
                    }
                } else {
                    G.unite(i, j);
                }
            }
        }
    }
    dd[u][v] = true;
    used[u][v] = !G.same(u, v);
    cc -= used[u][v];
    return used[u][v];
}

void initialize(int n) {
    cc = n;
    G = dsu(n);
    used.resize(n, vector<bool>(n, false));
    dd = used;
}

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