oj.uz

Submission #578291

# Submission time Handle Problem Language Result Execution time Memory
578291 2022-06-16T10:27:42 Z johnf Game (APIO22_game) C++17
2 / 100
 1 ms 216 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Incorrect 1 ms 208 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Incorrect 1 ms 208 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Incorrect 1 ms 208 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Incorrect 1 ms 208 KB Wrong Answer[1]
14 Halted 0 ms 0 KB -