oj.uz

Submission #630453

# Submission time Handle Problem Language Result Execution time Memory
630453 2022-08-16T11:33:32 Z Ooops_sorry Game (APIO22_game) C++17
12 / 100
 22 ms 29176 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const int N = 3e5 + 10, INF = 1e9, K = 500;
int n, k, in_block[N], out_block[N], in[N], out[N], block[N], cnt[N];
bool used[N];
vector<int> g[N], gr[N];
bool cycle = 0;
set<int> need;

void dfs_block(int v) {
    if (v >= k && out_block[v] < in_block[v]) {
        cycle = 1;
    }
    if (v >= k && !used[v] && out_block[v] == in_block[v]) {
        need.insert(in_block[v]);
        block[v] = in_block[v];
        used[v] = 1;
    }
    for (auto to : g[v]) {
        if (in_block[v] > in_block[to]) {
            in_block[to] = in_block[v];
            dfs_block(to);
        }
    }
}

void zhfs_block(int v) {
    if (v >= k && out_block[v] < in_block[v]) {
        cycle = 1;
    }
    if (v >= k && !used[v] && out_block[v] == in_block[v]) {
        need.insert(in_block[v]);
        block[v] = in_block[v];
        used[v] = 1;
    }
    for (auto to : gr[v]) {
        if (out_block[v] < out_block[to]) {
            out_block[to] = out_block[v];
            zhfs_block(to);
        }
    }
}

void dfs(int v) {
    cnt[v]++;
    assert(cnt[v] <= N / K);
    if (v >= k && out[v] <= in[v]) {
        cycle = 1;
    }
    for (auto to : g[v]) {
        if (block[v] == block[to] && in[v] > in[to]) {
            in[to] = in[v];
            dfs(to);
        }
    }
}

void zhfs(int v) {
    cnt[v]++;
    assert(cnt[v] <= N / K);
    if (v >= k && out[v] <= in[v]) {
        cycle = 1;
    }
    for (auto to : gr[v]) {
        if (block[v] == block[to] && out[v] < out[to]) {
            out[to] = out[v];
            zhfs(to);
        }
    }
}

int add_teleporter(int u, int v) {
    if (max(u, v) < k) {
        if (u >= v) {
            cycle = 1;
        }
    } else {
        g[u].pb(v);
        gr[v].pb(u);
        if (in_block[v] < in_block[u]) {
            in_block[v] = in_block[u];
            dfs_block(v);
        }
        if (out_block[u] > out_block[v]) {
            out_block[u] = out_block[v];
            zhfs_block(u);
        }
        for (auto v : need) {
            for (int vert = v * K; vert < min(k, (v + 1) * K); vert++) {
                zhfs(vert);
                dfs(vert);
            }
        }
        need.clear();
        if (block[v] == block[u] && in[v] < in[u]) {
            in[v] = in[u];
            dfs(v);
        }
        if (block[v] == block[u] && out[u] > out[v]) {
            out[u] = out[v];
            zhfs(u);
        }
    }
    return cycle;
}

void init(int n_, int k_) {
    n = n_, k = k_;
    for (int i = 0; i < n; i++) {
        in_block[i] = -INF, out_block[i] = INF;
        in[i] = -INF, out[i] = INF;
        block[i] = -(i + 1);
    }
    for (int i = 0; i < k; i++) {
        in_block[i] = out_block[i] = block[i] = i / K;
        in[i] = out[i] = i;
        if (i + 1 < k) {
            add_teleporter(i, i + 1);
        }
    }
}

#ifdef LOCAL

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int,int>> e(m);
    for (int i = 0; i < m; i++) {
        cin >> e[i].first >> e[i].second;
    }
    init(n, k);
    int i;
    for (i = 0; i < m; i++) {
        int res = add_teleporter(e[i].first, e[i].second);
        assert(res == 0 || res == 1);
        if (res == 1) {
            break;
        }
    }
    cout << i << endl;
    return 0;
}

#endif // LOCAL

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 10 ms 14372 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 10 ms 14372 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 8 ms 14404 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 8 ms 14416 KB Output is correct
11 Correct 7 ms 14352 KB Output is correct
12 Correct 8 ms 14416 KB Output is correct
13 Correct 9 ms 14416 KB Output is correct
14 Correct 8 ms 14416 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 11 ms 14424 KB Output is correct
17 Correct 8 ms 14428 KB Output is correct
18 Correct 7 ms 14416 KB Output is correct
19 Correct 8 ms 14416 KB Output is correct

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 10 ms 14372 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 8 ms 14404 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 8 ms 14416 KB Output is correct
11 Correct 7 ms 14352 KB Output is correct
12 Correct 8 ms 14416 KB Output is correct
13 Correct 9 ms 14416 KB Output is correct
14 Correct 8 ms 14416 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 11 ms 14424 KB Output is correct
17 Correct 8 ms 14428 KB Output is correct
18 Correct 7 ms 14416 KB Output is correct
19 Correct 8 ms 14416 KB Output is correct
20 Correct 8 ms 14416 KB Output is correct
21 Correct 8 ms 14416 KB Output is correct
22 Correct 9 ms 14416 KB Output is correct
23 Correct 10 ms 14416 KB Output is correct
24 Correct 11 ms 14416 KB Output is correct
25 Correct 10 ms 14496 KB Output is correct
26 Correct 10 ms 14464 KB Output is correct
27 Runtime error 22 ms 29176 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 10 ms 14372 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 8 ms 14404 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 8 ms 14416 KB Output is correct
11 Correct 7 ms 14352 KB Output is correct
12 Correct 8 ms 14416 KB Output is correct
13 Correct 9 ms 14416 KB Output is correct
14 Correct 8 ms 14416 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 11 ms 14424 KB Output is correct
17 Correct 8 ms 14428 KB Output is correct
18 Correct 7 ms 14416 KB Output is correct
19 Correct 8 ms 14416 KB Output is correct
20 Correct 8 ms 14416 KB Output is correct
21 Correct 8 ms 14416 KB Output is correct
22 Correct 9 ms 14416 KB Output is correct
23 Correct 10 ms 14416 KB Output is correct
24 Correct 11 ms 14416 KB Output is correct
25 Correct 10 ms 14496 KB Output is correct
26 Correct 10 ms 14464 KB Output is correct
27 Runtime error 22 ms 29176 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 10 ms 14372 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 8 ms 14416 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 8 ms 14416 KB Output is correct
8 Correct 8 ms 14404 KB Output is correct
9 Correct 7 ms 14416 KB Output is correct
10 Correct 8 ms 14416 KB Output is correct
11 Correct 7 ms 14352 KB Output is correct
12 Correct 8 ms 14416 KB Output is correct
13 Correct 9 ms 14416 KB Output is correct
14 Correct 8 ms 14416 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 11 ms 14424 KB Output is correct
17 Correct 8 ms 14428 KB Output is correct
18 Correct 7 ms 14416 KB Output is correct
19 Correct 8 ms 14416 KB Output is correct
20 Correct 8 ms 14416 KB Output is correct
21 Correct 8 ms 14416 KB Output is correct
22 Correct 9 ms 14416 KB Output is correct
23 Correct 10 ms 14416 KB Output is correct
24 Correct 11 ms 14416 KB Output is correct
25 Correct 10 ms 14496 KB Output is correct
26 Correct 10 ms 14464 KB Output is correct
27 Runtime error 22 ms 29176 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -