oj.uz

Submission #966797

# Submission time Handle Problem Language Result Execution time Memory
966797 2024-04-20T11:37:50 Z Nhoksocqt1 Game (APIO22_game) C++17
2 / 100
 9 ms 22100 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_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(numNode);
    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;
        } else {
            max_spe_from[i] = -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 = 0; k <= maxLog; ++k) {
        int mask = (1 << k) - 1;
        if((id_bucket[u] & mask) == (id_bucket[v] & mask)) {
            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();
            //cout << "MIN BUCKET TO " << u << ' ' << min_bucket_to[u] << '\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);
                if(k == maxLog)
                    return true;

                nodes.push_back(u);
            }

            for (int it = 0; it < sz(adjr[u]); ++it) {
                int v(adjr[u][it]);
                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 FROM " << u << ' ' << max_bucket_from[u] << '\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);
                if(k == maxLog)
                    return true;

                nodes.push_back(u);
            }

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

        mask = (1 << (k + 1)) - 1;
        for (int it = 0; it < sz(nodes); ++it) {
            int u(nodes[it]);
            for (int it = 0; it < sz(adj[u]); ++it) {
                int v(adj[u][it]);
                if((id_bucket[u] & mask) != (id_bucket[v] & mask))
                    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((id_bucket[u] & mask) != (id_bucket[v] & mask))
                    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 5 ms 21848 KB Output is correct
2 Correct 6 ms 21848 KB Output is correct
3 Correct 9 ms 21848 KB Output is correct
4 Correct 5 ms 21848 KB Output is correct
5 Correct 6 ms 21848 KB Output is correct
6 Correct 6 ms 21848 KB Output is correct
7 Correct 6 ms 21848 KB Output is correct

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 18.0

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

Subtask #4
0.0 / 30.0

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

Subtask #5
0.0 / 40.0

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