제출 #700850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700850		Forested	게임 (IOI14_game)	C++17	15 / 100	2 ms	468 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];
    }
};

mt19937 mt(998244353);
i32 m;
Vec<i32> deg;
Vec<Vec<i32>> rem;
set<pair<i32, i32>> st;
//UnionFindWithCounter uf;

void initialize(int n) {
    m = n;
    deg = Vec<i32>(m, m - 1);
    rem = Vec<Vec<i32>>(m, Vec<i32>(m, 1));
    REP(i, m) {
        rem[i][i] = 0;
    }
    //uf = UnionFindWithCounter(m);
}

void opt(i32 u, i32 v) {
    st.insert(make_pair(u, v));
    st.insert(make_pair(v, u));
    --deg[u];
    --deg[v];
    rem[u][v] = rem[v][u] = 0;
    if (deg[u] == 1) {
        REP(x, m) {
            if (rem[u][x]) {
                opt(u, x);
            }
        }
    }
    if (deg[v] == 1) {
        REP(x, m) {
            if (rem[v][x]) {
                opt(v, x);
            }
        }
    }
}

int hasEdge(int u, int v) {
    if (m == 2) {
        return 1;
    }
    if (rem[u][v]) {
    --deg[u];
    --deg[v];
    rem[u][v] = rem[v][u] = 0;
    if (deg[u] == 1) {
        REP(x, m) {
            if (rem[u][x]) {
                opt(u, x);
            }
        }
    }
    if (deg[v] == 1) {
        REP(x, m) {
            if (rem[v][x]) {
                opt(v, x);
            }
        }
    }
    }
    if (st.count(make_pair(u, v))) {
        return 1;
    } else {
        return 0;
    }
}

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