Submission #700336

#	Time	Username	Problem	Language	Result	Execution time	Memory
700336		Forested	Game (IOI14_game)	C++17	42 / 100	1090 ms	1384 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;

i32 m;
Vec<Vec<i32>> rem;

void initialize(int n) {
    m = n;
    rem = Vec<Vec<i32>>(m, Vec<i32>(m, 1));
}

int hasEdge(int u, int v) {
    rem[u][v] = rem[v][u] = 0;
    Vec<i32> seen(m, 0);
    queue<i32> que;
    seen[0] = 0;
    que.push(0);
    while (!que.empty()) {
        i32 x = que.front();
        que.pop();
        REP(y, m) {
            if (rem[x][y] && !seen[y]) {
                seen[y] = 1;
                que.push(y);
            }
        }
    }
    if (accumulate(ALL(seen), 0) == m) {
        return 0;
    } else {
        rem[u][v] = rem[v][u] = 1;
        return 1;
    }
}

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