Submission #700367

#	Time	Username	Problem	Language	Result	Execution time	Memory
700367		Forested	Game (IOI14_game)	C++17	0 / 100	1 ms	256 KiB

game

#include "game.h"

#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;

#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    } else {
        return false;
    }
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    } else {
        return false;
    }
}

constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;

class UnionFindWithCounter {
    Vec<i32> par;
    Vec<i32> cnt;
    
    i32 root(i32 x) {
        if (par[x] < 0) {
            return x;
        } else {
            return par[x] = root(par[x]);
        }
    }
    
public:
    UnionFindWithCounter() = default;
    UnionFindWithCounter(i32 n) : par(n, -1), cnt(n, 0) {}
    
    bool same(i32 x, i32 y) {
        x = root(x);
        y = root(y);
        return x == y;
    }
    
    void unite(i32 x, i32 y) {
        x = root(x);
        y = root(y);
        if (x == y) {
            return;
        }
        if (-par[x] > -par[y]) {
            swap(x, y);
        }
        cnt[y] += cnt[x];
        cnt[x] = 0;
        par[y] += par[x];
        par[x] = y;
    }
    
    void increase(i32 x) {
        x = root(x);
        ++cnt[x];
    }
    
    i32 access(i32 x) {
        x = root(x);
        return cnt[x];
    }
    
    i32 size(i32 x) {
        x = root(x);
        return -par[x];
    }
};

i32 m;
UnionFindWithCounter uf;

void initialize(int n) {
    m = n;
    uf = UnionFindWithCounter(m);
}

i32 cut(i32 v) {
    return v * (m - v) + v * (v - 1) / 2 - v + 1;
}

int hasEdge(int u, int v) {
    i32 sz_u = uf.size(u);
    i32 cnt_u = uf.access(u);
    i32 sz_v = uf.size(v);
    i32 cnt_v = uf.access(v);
    if (cnt_u == cut(sz_u) - 1 || cnt_v == cut(sz_v) - 1) {
        uf.unite(u, v);
        return 1;
    } else {
        uf.increase(u);
        uf.increase(v);
        return 0;
    }
}

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