Submission #576181

#	Time	Username	Problem	Language	Result	Execution time	Memory
576181		elazarkoren	Game (IOI14_game)	C++17	42 / 100	1089 ms	8664 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

mt19937 rng(time(0));

struct Dsu {
    int n;
    vi par, sz;
    Dsu() {}
    Dsu(int n): n(n) {
        par.resize(n), sz.resize(n, 1);
        iota(all(par), 0);
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    bool Union(int a, int b) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) return false;
        if (sz[pa] < sz[pb]) swap(pa, pb);
        par[pb] = pa;
        sz[pa] += sz[pb];
        return true;
    }
};

const int MAX_N = 1505;

bitset<MAX_N> graph[MAX_N];
set<pii> edges;
set<pii> tree_e;
int n;

void initialize(int N) {
    n = N;
    vii e;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            graph[i][j] = graph[j][i] = 1;
            edges.insert({i, j});
            e.push_back({i, j});
        }
    }
    Dsu dsu(n);
    shuffle(all(e), rng);
    for (pii p : e) {
        if (dsu.Union(p.x, p.y)) {
            tree_e.insert(p);
        }
    }
}

bitset<MAX_N> visited;
void Dfs(vvi &tree, int node, int parent) {
    visited[node] = true;
    for (int neighbor : tree[node]) {
        if (neighbor != parent) {
            Dfs(tree, neighbor, node);
        }
    }
}

const int block = 1e4;

int hasEdge(int u, int v) {
    if (u > v) swap(u, v);
    graph[u][v] = graph[v][u] = 0;
    if (!tree_e.count({u, v})) {
        edges.erase({u, v});
        return 0;
    }
    if (edges.size() < block) {
        Dsu dsu(n);
        set<pii> next;
        vii e(all(edges));
        shuffle(all(e), rng);
        for (auto [a, b] : e) {
            if (a != u || b != v) {
                if (dsu.Union(a, b)) next.insert({a, b});
            }
        }
        if (dsu.sz[dsu.Find(0)] != n) return 1;
        edges.erase(edges.find({u, v}));
        tree_e = next;
        return 0;
    }
    vvi tree(n);
    for (auto [a, b] : tree_e) {
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    visited.reset();
    Dfs(tree, u, v);
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        if ((visited & graph[i]).any()) {
            tree_e.erase(tree_e.find({u, v}));
            for (int j = 0; j < n; j++) {
                if (visited[j] && graph[i][j]) {
                    if (i > j) swap(i, j);
                    tree_e.insert({i, j});
                    break;
                }
            }
            edges.erase({u, v});
            return 0;
        }
    }
    graph[u][v] = graph[v][u] = 1;
    return 1;
}

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