Submission #578293

#	Time	Username	Problem	Language	Result	Execution time	Memory
578293		johnf	Game (APIO22_game)	C++17	30 / 100	1298 ms	4036 KiB

game

#include "game.h"
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

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

using ll = long long;
using ld = long double;
using vi = vector<int>;

template <class T>
bool uin(T &a, T b) {
    return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n, k;

namespace sub3 {
vector<vi> adj;
stack<int> st;
int id = 0;
vi low, num;

bool eligible() { return n <= 1000; }

void init() {
    adj.assign(n, {});
    fore(i, 0, k - 2) { adj[i].pb(i + 1); }
}

bool dfs(int u) {
    low[u] = num[u] = ++id;
    st.push(u);
    for (auto v : adj[u]) {
        if (num[v]) {
            uin(low[u], num[v]);
        } else {
            if (dfs(v)) {
                return 1;
            }
            uin(low[u], low[v]);
        }
    }
    if (low[u] == num[u]) {
        int v;
        vector<int> vec;
        do {
            v = st.top();
            st.pop();
            low[v] = num[v] = 1e9;
            vec.pb(v);
        } while (v != u);
        if (vec.size() >= 2) {
            for (auto x : vec) {
                if (x < k) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int add_teleporter(int u, int v) {
    if (u == v) {
        if (u < k) {
            return 1;
        }
    } else {
        adj[u].pb(v);
    }
    low = num = vi(n);
    id = 0;
    for0(i, n) {
        if (!num[i]) {
            if (dfs(i)) {
                return 1;
            }
        }
    }
    return 0;
}
}

namespace sub4 {
vector<vi> adj, adj_rev;
vector<int> min_reach, max_reach;

bool eligible() { return k <= 1000; }

void init() {
    adj.assign(n, {});
    adj_rev.assign(n, {});
    min_reach.assign(n, k);
    max_reach.assign(n, -1);
    for0(i, k) {
        min_reach[i] = i + 1;
        max_reach[i] = i;
    }
}

int add_teleporter(int u, int v) {
    if (u < k && v < k) {
        if (u >= v) {
            return 1;
        }
        return 0;
    }
    adj[u].pb(v);
    adj_rev[v].pb(u);
    queue<int> q;
    if (uin(min_reach[u], min_reach[v])) {
        q.push(u);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (min_reach[u] <= max_reach[u]) {
            return 1;
        }
        for (auto v : adj_rev[u]) {
            if (uin(min_reach[v], min_reach[u])) {
                q.push(v);
            }
        }
    }
    if (uax(max_reach[v], max_reach[u])) {
        q.push(v);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (min_reach[u] <= max_reach[u]) {
            return 1;
        }
        for (auto v : adj[u]) {
            if (uax(max_reach[v], max_reach[u])) {
                q.push(v);
            }
        }
    }
    return 0;
}
};

void init(int N, int K) {
    n = N;
    k = K;
    if (sub3::eligible()) {
        sub3::init();
    } else
    if (sub4::eligible()) {
        sub4::init();
    }
}

int add_teleporter(int u, int v) {
    if (sub3::eligible()) {
        return sub3::add_teleporter(u, v);
    } else
    if (sub4::eligible()) {
        return sub4::add_teleporter(u, v);
    }
}

Compilation message (stderr)

game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:186:1: warning: control reaches end of non-void function [-Wreturn-type]
  186 | }
      | ^

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40