oj.uz

Submission #966887

# Submission time Handle Problem Language Result Execution time Memory
966887 2024-04-20T14:30:40 Z Nhoksocqt1 Game (APIO22_game) C++17
60 / 100
 4000 ms 90624 KB 
#ifndef Nhoksocqt1
    #include "game.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(2);
//#define HAHA
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 300005;
const int MAXM = 800005;

vector<int> adj[MAXN], adjr[MAXN];
int min_bucket_to[MAXN][20], max_bucket_from[MAXN][20];
int id_bucket[MAXN], min_same[MAXN], min_spe_to[MAXN], max_spe_from[MAXN];
int numBlock, maxLog, numNode, numSpecial;
bool dx[MAXN];

void init(int _N, int _K) {
    numNode = _N, numSpecial = _K;
    maxLog = 31 - __builtin_clz(numSpecial);
    for (int i = 0; i < numNode; ++i) {
        if(i < numSpecial) {
            min_spe_to[i] = max_spe_from[i] = i;
            for (int j = 0; j <= maxLog; ++j)
                min_bucket_to[i][j] = max_bucket_from[i][j] = i >> j & 1;

            id_bucket[i] = i;
            min_same[i] = 0;
        } else {
            max_spe_from[i] = -1;
            min_same[i] = maxLog + 1;
            min_spe_to[i] = numSpecial;
            for (int j = 0; j <= maxLog; ++j)
                min_bucket_to[i][j] = 2, max_bucket_from[i][j] = -1;
        }
    }
}

bool brute(int u, int v) {
    queue<int> qu;
    if(min_spe_to[u] > min(min_spe_to[v], v)) {
        min_spe_to[u] = min(min_spe_to[v], v);
        qu.push(u);
    }

    while(sz(qu)) {
        int u(qu.front()); qu.pop();
        if(max_spe_from[u] >= min_spe_to[u])
            return true;

        for (int it = 0; it < sz(adjr[u]); ++it) {
            int v(adjr[u][it]);
            if(min_spe_to[v] > min_spe_to[u]) {
                min_spe_to[v] = min_spe_to[u];
                qu.push(v);
            }
        }
    }

    int max_spe_from_now = max(max_spe_from[u], (u < numSpecial ? u : -1));
    if(max_spe_from[v] < max_spe_from_now) {
        max_spe_from[v] = max_spe_from_now;
        qu.push(v);
    }

    while(sz(qu)) {
        int u(qu.front()); qu.pop();
        if(u >= numSpecial && max_spe_from[u] >= min_spe_to[u])
            return true;

        for (int it = 0; it < sz(adj[u]); ++it) {
            int v(adj[u][it]);
            if(max_spe_from[v] < max_spe_from[u]) {
                max_spe_from[v] = max_spe_from[u];
                qu.push(v);
            }
        }
    }

    return false;
}

bool magicFunc(int u, int v) {
    queue<int> quMax, quMin;
    for (int k = maxLog; k >= 0; --k) {
        if(max(min_same[u], min_same[v]) <= k + 1 && (id_bucket[u] >> (k + 1)) == (id_bucket[v] >> (k + 1))) {
            if(min_bucket_to[u][k] > min_bucket_to[v][k]) {
                min_bucket_to[u][k] = min_bucket_to[v][k];
                quMin.push(u);
            }

            if(max_bucket_from[v][k] < max_bucket_from[u][k]) {
                max_bucket_from[v][k] = max_bucket_from[u][k];
                quMax.push(v);
            }
        }

        vector<int> nodes;
        while(sz(quMin)) {
            int u(quMin.front()); quMin.pop();
            if(max_bucket_from[u][k] > min_bucket_to[u][k])
                return true;

            if(max_bucket_from[u][k] == min_bucket_to[u][k]) {
                id_bucket[u] |= (max_bucket_from[u][k] << k);
                min_same[u] = min(min_same[u], k);
                if(k == 0)
                    return true;

                nodes.push_back(u);
            }

            //cout << "MIN BUCKET " << k << " TO " << u << ' ' << min_same[u] << ' ' << min_bucket_to[u][k] << '\n';
            for (int it = 0; it < sz(adjr[u]); ++it) {
                int v(adjr[u][it]);
                if(min_same[v] > k + 1 || (id_bucket[u] >> (k + 1)) != (id_bucket[v] >> (k + 1)))
                    continue;

                if(min_bucket_to[v][k] > min_bucket_to[u][k]) {
                    min_bucket_to[v][k] = min_bucket_to[u][k];
                    quMin.push(v);
                }
            }
        }

        while(sz(quMax)) {
            int u(quMax.front()); quMax.pop();
            //cout << "MAX BUCKET " << k << " FROM " << u << ' ' << min_same[u] << ' ' << max_bucket_from[u][k] << '\n';
            if(max_bucket_from[u][k] > min_bucket_to[u][k])
                return true;

            if(max_bucket_from[u][k] == min_bucket_to[u][k]) {
                id_bucket[u] |= (max_bucket_from[u][k] << k);
                min_same[u] = min(min_same[u], k);
                if(k == 0)
                    return true;

                nodes.push_back(u);
            }

            for (int it = 0; it < sz(adj[u]); ++it) {
                int v(adj[u][it]);
                if(min_same[v] > k + 1 || (id_bucket[u] >> (k + 1)) != (id_bucket[v] >> (k + 1)))
                    continue;

                if(max_bucket_from[v][k] < max_bucket_from[u][k]) {
                    max_bucket_from[v][k] = max_bucket_from[u][k];
                    quMax.push(v);
                }
            }
        }

        for (int it = 0; it < sz(nodes); ++it) {
            int u(nodes[it]);
            //cout << u << ' ' << min_same[u] << ' ' << id_bucket[u] << ":\n";
            for (int it = 0; it < sz(adj[u]); ++it) {
                int v(adj[u][it]);
                //cout << v << ' ' << min_same[v] << ' ' << id_bucket[v] << ' ' << (id_bucket[v] >> k) << ' ' << (id_bucket[u] >> k) << '\n';
                if(max(min_same[u], min_same[v]) > k || (id_bucket[u] >> k) != (id_bucket[v] >> k))
                    continue;

                if(min_bucket_to[u][k - 1] > min_bucket_to[v][k - 1]) {
                    min_bucket_to[u][k - 1] = min_bucket_to[v][k - 1];
                    quMin.push(u);
                }
            }

            for (int it = 0; it < sz(adjr[u]); ++it) {
                int v(adjr[u][it]);
                if(max(min_same[u], min_same[v]) > k || (id_bucket[u] >> k) != (id_bucket[v] >> k))
                    continue;

                if(max_bucket_from[u][k - 1] < max_bucket_from[v][k - 1]) {
                    max_bucket_from[u][k - 1] = max_bucket_from[v][k - 1];
                    quMax.push(u);
                }
            }
        }
    }

    return false;
}

int add_teleporter(int u, int v) {
    if(max(u, v) < numSpecial)
        return (u >= v);

    if(u == v)
        return false;

    adj[u].push_back(v);
    adjr[v].push_back(u);

    //cout << brute(u, v) << ' ' << magicFunc(u, v) << '\n'; return false;
    /*if(numNode <= 30000 && numSpecial <= 1000) {
        return brute(u, v);
    } else*/ {
        return magicFunc(u, v);
    }

    return false;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "game"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    int n, k, m;
    cin >> n >> k >> m;

    init(n, k);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        //u = Random(0, n - 2), v = Random(max(k, u + 1), n - 1); if(Random(0, 1)) swap(u, v);
        int ans = add_teleporter(u, v);
        cout << "ANSWER FOR EDGE " << u << " TO " << v << ": " << ans << '\n';
        if(ans == 1)
            break;
    }

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
2.0 / 2.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct
4 Correct 4 ms 23156 KB Output is correct
5 Correct 5 ms 23128 KB Output is correct
6 Correct 5 ms 23128 KB Output is correct
7 Correct 4 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 5 ms 23128 KB Output is correct
10 Correct 5 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23216 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 5 ms 23128 KB Output is correct
15 Correct 5 ms 23128 KB Output is correct
16 Correct 5 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 5 ms 23128 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct
4 Correct 4 ms 23156 KB Output is correct
5 Correct 5 ms 23128 KB Output is correct
6 Correct 5 ms 23128 KB Output is correct
7 Correct 4 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 5 ms 23128 KB Output is correct
10 Correct 5 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23216 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 5 ms 23128 KB Output is correct
15 Correct 5 ms 23128 KB Output is correct
16 Correct 5 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 5 ms 23128 KB Output is correct
20 Correct 6 ms 23128 KB Output is correct
21 Correct 5 ms 23128 KB Output is correct
22 Correct 5 ms 23128 KB Output is correct
23 Correct 5 ms 23224 KB Output is correct
24 Correct 5 ms 23128 KB Output is correct
25 Correct 6 ms 23236 KB Output is correct
26 Correct 8 ms 23384 KB Output is correct
27 Correct 7 ms 23256 KB Output is correct
28 Correct 6 ms 23128 KB Output is correct
29 Correct 7 ms 23128 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct
4 Correct 4 ms 23156 KB Output is correct
5 Correct 5 ms 23128 KB Output is correct
6 Correct 5 ms 23128 KB Output is correct
7 Correct 4 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 5 ms 23128 KB Output is correct
10 Correct 5 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23216 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 5 ms 23128 KB Output is correct
15 Correct 5 ms 23128 KB Output is correct
16 Correct 5 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 5 ms 23128 KB Output is correct
20 Correct 6 ms 23128 KB Output is correct
21 Correct 5 ms 23128 KB Output is correct
22 Correct 5 ms 23128 KB Output is correct
23 Correct 5 ms 23224 KB Output is correct
24 Correct 5 ms 23128 KB Output is correct
25 Correct 6 ms 23236 KB Output is correct
26 Correct 8 ms 23384 KB Output is correct
27 Correct 7 ms 23256 KB Output is correct
28 Correct 6 ms 23128 KB Output is correct
29 Correct 7 ms 23128 KB Output is correct
30 Correct 29 ms 29004 KB Output is correct
31 Correct 10 ms 27736 KB Output is correct
32 Correct 25 ms 29424 KB Output is correct
33 Correct 21 ms 29272 KB Output is correct
34 Correct 64 ms 29900 KB Output is correct
35 Correct 54 ms 29684 KB Output is correct
36 Correct 65 ms 29596 KB Output is correct
37 Correct 70 ms 29428 KB Output is correct
38 Correct 52 ms 29368 KB Output is correct
39 Correct 57 ms 29372 KB Output is correct
40 Correct 78 ms 30452 KB Output is correct
41 Correct 51 ms 29512 KB Output is correct
42 Correct 38 ms 29516 KB Output is correct
43 Correct 70 ms 29732 KB Output is correct
44 Correct 91 ms 30032 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct
4 Correct 4 ms 23156 KB Output is correct
5 Correct 5 ms 23128 KB Output is correct
6 Correct 5 ms 23128 KB Output is correct
7 Correct 4 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 5 ms 23128 KB Output is correct
10 Correct 5 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23216 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 5 ms 23128 KB Output is correct
15 Correct 5 ms 23128 KB Output is correct
16 Correct 5 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 5 ms 23128 KB Output is correct
20 Correct 6 ms 23128 KB Output is correct
21 Correct 5 ms 23128 KB Output is correct
22 Correct 5 ms 23128 KB Output is correct
23 Correct 5 ms 23224 KB Output is correct
24 Correct 5 ms 23128 KB Output is correct
25 Correct 6 ms 23236 KB Output is correct
26 Correct 8 ms 23384 KB Output is correct
27 Correct 7 ms 23256 KB Output is correct
28 Correct 6 ms 23128 KB Output is correct
29 Correct 7 ms 23128 KB Output is correct
30 Correct 29 ms 29004 KB Output is correct
31 Correct 10 ms 27736 KB Output is correct
32 Correct 25 ms 29424 KB Output is correct
33 Correct 21 ms 29272 KB Output is correct
34 Correct 64 ms 29900 KB Output is correct
35 Correct 54 ms 29684 KB Output is correct
36 Correct 65 ms 29596 KB Output is correct
37 Correct 70 ms 29428 KB Output is correct
38 Correct 52 ms 29368 KB Output is correct
39 Correct 57 ms 29372 KB Output is correct
40 Correct 78 ms 30452 KB Output is correct
41 Correct 51 ms 29512 KB Output is correct
42 Correct 38 ms 29516 KB Output is correct
43 Correct 70 ms 29732 KB Output is correct
44 Correct 91 ms 30032 KB Output is correct
45 Correct 296 ms 78332 KB Output is correct
46 Correct 18 ms 66904 KB Output is correct
47 Correct 18 ms 66904 KB Output is correct
48 Correct 493 ms 86116 KB Output is correct
49 Correct 330 ms 85832 KB Output is correct
50 Correct 1873 ms 85924 KB Output is correct
51 Correct 1417 ms 86916 KB Output is correct
52 Correct 873 ms 85712 KB Output is correct
53 Correct 1334 ms 86512 KB Output is correct
54 Correct 1606 ms 85480 KB Output is correct
55 Correct 2440 ms 88224 KB Output is correct
56 Correct 3494 ms 90500 KB Output is correct
57 Correct 842 ms 79472 KB Output is correct
58 Correct 879 ms 79628 KB Output is correct
59 Correct 867 ms 79648 KB Output is correct
60 Correct 1550 ms 81852 KB Output is correct
61 Correct 1897 ms 81988 KB Output is correct
62 Correct 1183 ms 82268 KB Output is correct
63 Correct 990 ms 78688 KB Output is correct
64 Correct 2770 ms 90624 KB Output is correct
65 Correct 778 ms 82772 KB Output is correct
66 Correct 636 ms 78532 KB Output is correct
67 Correct 1273 ms 86764 KB Output is correct
68 Correct 282 ms 75920 KB Output is correct
69 Correct 69 ms 69676 KB Output is correct
70 Correct 1210 ms 84088 KB Output is correct
71 Correct 395 ms 78972 KB Output is correct
72 Correct 294 ms 74504 KB Output is correct
73 Correct 922 ms 82536 KB Output is correct
74 Execution timed out 4056 ms 90284 KB Time limit exceeded
75 Halted 0 ms 0 KB -