oj.uz

Submission #966740

# Submission time Handle Problem Language Result Execution time Memory
966740 2024-04-20T09:26:56 Z Nhoksocqt1 Game (APIO22_game) C++17
60 / 100
 4000 ms 51312 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(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

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

vector<ii> adj1[MAXN];
vector<int> adj[MAXN], adjr[MAXN];
int min_bucket_to[MAXN], max_bucket_from[MAXN], min_spe_to[MAXN], max_spe_from[MAXN];
int low[MAXN], num[MAXN], L[BLOCK], R[BLOCK], id_block[MAXN], numBlock, numNode, numEdge, numSpecial;
bool dx[MAXN], dxe[MAXM];

void init(int _N, int _K) {
    numNode = _N, numSpecial = _K, numEdge = 0;
    for (int i = 0; i + 1 < numSpecial; ++i)
        adj1[i].push_back(ii(i + 1, numEdge++));

    for (int i = 0; i < numNode; ++i) {
        min_spe_to[i] = (i < numSpecial) ? i : numSpecial;
        max_spe_from[i] = (i < numSpecial) ? i : -1;
    }

    numBlock = (numSpecial + BLOCK - 1) / BLOCK;
    for (int i = 0; i < numBlock; ++i) {
        L[i] = i * BLOCK;
        R[i] = min(numSpecial, (i + 1) * BLOCK - 1);
        for (int j = L[i]; j <= R[i]; ++j) {
            min_bucket_to[j] = max_bucket_from[j] = i;
            id_block[j] = i;
        }
    }

    for (int i = numSpecial; i < numNode; ++i) {
        max_bucket_from[i] = -1;
        min_bucket_to[i] = numBlock;
    }
}

stack<int> st;
bool tarjan(int u) {
    low[u] = num[u] = ++num[numNode];
    st.push(u);

    for (int it = 0; it < sz(adj1[u]); ++it) {
        int v(adj1[u][it].fi), id(adj1[u][it].se);
        if(!dxe[id]) {
            dxe[id] = 1;
            if(!num[v]) {
                if(tarjan(v))
                    return true;

                low[u] = min(low[u], low[v]);
            } else {
                low[u] = min(low[u], num[v]);
            }
        }
    }

    if(low[u] == num[u]) {
        int v, cnt(0);
        bool has_special(0);
        do {
            v = st.top(); st.pop();
            low[v] = num[v] = 1e9+7;
            has_special |= (v < numSpecial), ++cnt;
        } while(v != u);

        return (cnt > 1 && has_special);
    }

    return false;
}

bool sub3(int u, int v) {
    adj1[u].push_back(ii(v, numEdge++));
    for (int i = 0; i <= numNode; ++i)
        low[i] = num[i] = 0;

    while(sz(st))
        st.pop();

    for (int i = 0; i < numEdge; ++i)
        dxe[i] = 0;

    for (int i = 0; i < numSpecial; ++i) {
        if(!num[i] && tarjan(i))
            return true;
    }

    return false;
}

bool brute(int u, int v) {
    adj[u].push_back(v);
    adjr[v].push_back(u);

    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) {
    adj[u].push_back(v);
    adjr[v].push_back(u);

    queue<int> qu;
    if(min_bucket_to[u] > min_bucket_to[v]) {
        min_bucket_to[u] = min_bucket_to[v];
        qu.push(u);
    }

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

        //cout << "MIN BUCKET TO " << u << ' ' << min_bucket_to[u] << '\n';
        if(max_bucket_from[u] == min_bucket_to[u])
            nodes.push_back(u);

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

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

    while(sz(qu)) {
        int u(qu.front()); qu.pop();
        if(max_bucket_from[u] > min_bucket_to[u])
            return true;

        //cout << "MAX BUCKET FROM " << u << ' ' << max_bucket_from[u] << '\n';
        if(max_bucket_from[u] == min_bucket_to[u])
            nodes.push_back(u);

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

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

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

    while(sz(qu)) {
        int u(qu.front()); qu.pop();
        //cout << "MIN SPE TO " << u << ' ' << min_spe_to[u] << '\n';
        //cout << "MAX SPE FROM " << u << ' ' << max_spe_from[u] << '\n';
        if(u >= numSpecial && 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(max_bucket_from[v] == min_bucket_to[v] && max_bucket_from[u] == max_bucket_from[v] && min_spe_to[v] > min_spe_to[u]) {
                min_spe_to[v] = min_spe_to[u];
                qu.push(v);
            }
        }

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

    return false;
}

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

    if(u == v)
        return false;

    if(numNode <= 1000) {
        return sub3(u, v);
    } else
        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;
        int ans = add_teleporter(u, v);
        cout << "ANSWER FOR EDGE " << u << " TO " << v << ": " << ans << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30804 KB Output is correct
2 Correct 8 ms 30552 KB Output is correct
3 Correct 8 ms 30552 KB Output is correct
4 Correct 9 ms 30552 KB Output is correct
5 Correct 7 ms 30680 KB Output is correct
6 Correct 7 ms 30552 KB Output is correct
7 Correct 7 ms 30704 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30804 KB Output is correct
2 Correct 8 ms 30552 KB Output is correct
3 Correct 8 ms 30552 KB Output is correct
4 Correct 9 ms 30552 KB Output is correct
5 Correct 7 ms 30680 KB Output is correct
6 Correct 7 ms 30552 KB Output is correct
7 Correct 7 ms 30704 KB Output is correct
8 Correct 8 ms 30552 KB Output is correct
9 Correct 6 ms 30664 KB Output is correct
10 Correct 7 ms 30552 KB Output is correct
11 Correct 7 ms 30552 KB Output is correct
12 Correct 6 ms 30552 KB Output is correct
13 Correct 7 ms 30552 KB Output is correct
14 Correct 7 ms 30660 KB Output is correct
15 Correct 8 ms 30480 KB Output is correct
16 Correct 7 ms 30804 KB Output is correct
17 Correct 7 ms 30552 KB Output is correct
18 Correct 7 ms 30552 KB Output is correct
19 Correct 7 ms 30552 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30804 KB Output is correct
2 Correct 8 ms 30552 KB Output is correct
3 Correct 8 ms 30552 KB Output is correct
4 Correct 9 ms 30552 KB Output is correct
5 Correct 7 ms 30680 KB Output is correct
6 Correct 7 ms 30552 KB Output is correct
7 Correct 7 ms 30704 KB Output is correct
8 Correct 8 ms 30552 KB Output is correct
9 Correct 6 ms 30664 KB Output is correct
10 Correct 7 ms 30552 KB Output is correct
11 Correct 7 ms 30552 KB Output is correct
12 Correct 6 ms 30552 KB Output is correct
13 Correct 7 ms 30552 KB Output is correct
14 Correct 7 ms 30660 KB Output is correct
15 Correct 8 ms 30480 KB Output is correct
16 Correct 7 ms 30804 KB Output is correct
17 Correct 7 ms 30552 KB Output is correct
18 Correct 7 ms 30552 KB Output is correct
19 Correct 7 ms 30552 KB Output is correct
20 Correct 8 ms 30552 KB Output is correct
21 Correct 7 ms 30552 KB Output is correct
22 Correct 8 ms 30552 KB Output is correct
23 Correct 7 ms 30720 KB Output is correct
24 Correct 19 ms 30836 KB Output is correct
25 Correct 52 ms 30748 KB Output is correct
26 Correct 64 ms 31056 KB Output is correct
27 Correct 80 ms 31276 KB Output is correct
28 Correct 33 ms 30552 KB Output is correct
29 Correct 46 ms 31064 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30804 KB Output is correct
2 Correct 8 ms 30552 KB Output is correct
3 Correct 8 ms 30552 KB Output is correct
4 Correct 9 ms 30552 KB Output is correct
5 Correct 7 ms 30680 KB Output is correct
6 Correct 7 ms 30552 KB Output is correct
7 Correct 7 ms 30704 KB Output is correct
8 Correct 8 ms 30552 KB Output is correct
9 Correct 6 ms 30664 KB Output is correct
10 Correct 7 ms 30552 KB Output is correct
11 Correct 7 ms 30552 KB Output is correct
12 Correct 6 ms 30552 KB Output is correct
13 Correct 7 ms 30552 KB Output is correct
14 Correct 7 ms 30660 KB Output is correct
15 Correct 8 ms 30480 KB Output is correct
16 Correct 7 ms 30804 KB Output is correct
17 Correct 7 ms 30552 KB Output is correct
18 Correct 7 ms 30552 KB Output is correct
19 Correct 7 ms 30552 KB Output is correct
20 Correct 8 ms 30552 KB Output is correct
21 Correct 7 ms 30552 KB Output is correct
22 Correct 8 ms 30552 KB Output is correct
23 Correct 7 ms 30720 KB Output is correct
24 Correct 19 ms 30836 KB Output is correct
25 Correct 52 ms 30748 KB Output is correct
26 Correct 64 ms 31056 KB Output is correct
27 Correct 80 ms 31276 KB Output is correct
28 Correct 33 ms 30552 KB Output is correct
29 Correct 46 ms 31064 KB Output is correct
30 Correct 28 ms 31832 KB Output is correct
31 Correct 16 ms 31320 KB Output is correct
32 Correct 26 ms 33368 KB Output is correct
33 Correct 23 ms 32600 KB Output is correct
34 Correct 948 ms 32856 KB Output is correct
35 Correct 335 ms 33152 KB Output is correct
36 Correct 49 ms 33284 KB Output is correct
37 Correct 43 ms 33492 KB Output is correct
38 Correct 39 ms 32320 KB Output is correct
39 Correct 34 ms 32832 KB Output is correct
40 Correct 754 ms 33004 KB Output is correct
41 Correct 153 ms 32856 KB Output is correct
42 Correct 108 ms 32672 KB Output is correct
43 Correct 46 ms 33096 KB Output is correct
44 Correct 417 ms 33000 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30804 KB Output is correct
2 Correct 8 ms 30552 KB Output is correct
3 Correct 8 ms 30552 KB Output is correct
4 Correct 9 ms 30552 KB Output is correct
5 Correct 7 ms 30680 KB Output is correct
6 Correct 7 ms 30552 KB Output is correct
7 Correct 7 ms 30704 KB Output is correct
8 Correct 8 ms 30552 KB Output is correct
9 Correct 6 ms 30664 KB Output is correct
10 Correct 7 ms 30552 KB Output is correct
11 Correct 7 ms 30552 KB Output is correct
12 Correct 6 ms 30552 KB Output is correct
13 Correct 7 ms 30552 KB Output is correct
14 Correct 7 ms 30660 KB Output is correct
15 Correct 8 ms 30480 KB Output is correct
16 Correct 7 ms 30804 KB Output is correct
17 Correct 7 ms 30552 KB Output is correct
18 Correct 7 ms 30552 KB Output is correct
19 Correct 7 ms 30552 KB Output is correct
20 Correct 8 ms 30552 KB Output is correct
21 Correct 7 ms 30552 KB Output is correct
22 Correct 8 ms 30552 KB Output is correct
23 Correct 7 ms 30720 KB Output is correct
24 Correct 19 ms 30836 KB Output is correct
25 Correct 52 ms 30748 KB Output is correct
26 Correct 64 ms 31056 KB Output is correct
27 Correct 80 ms 31276 KB Output is correct
28 Correct 33 ms 30552 KB Output is correct
29 Correct 46 ms 31064 KB Output is correct
30 Correct 28 ms 31832 KB Output is correct
31 Correct 16 ms 31320 KB Output is correct
32 Correct 26 ms 33368 KB Output is correct
33 Correct 23 ms 32600 KB Output is correct
34 Correct 948 ms 32856 KB Output is correct
35 Correct 335 ms 33152 KB Output is correct
36 Correct 49 ms 33284 KB Output is correct
37 Correct 43 ms 33492 KB Output is correct
38 Correct 39 ms 32320 KB Output is correct
39 Correct 34 ms 32832 KB Output is correct
40 Correct 754 ms 33004 KB Output is correct
41 Correct 153 ms 32856 KB Output is correct
42 Correct 108 ms 32672 KB Output is correct
43 Correct 46 ms 33096 KB Output is correct
44 Correct 417 ms 33000 KB Output is correct
45 Correct 227 ms 43004 KB Output is correct
46 Correct 13 ms 31592 KB Output is correct
47 Correct 11 ms 31320 KB Output is correct
48 Correct 343 ms 51312 KB Output is correct
49 Correct 243 ms 49944 KB Output is correct
50 Execution timed out 4057 ms 49212 KB Time limit exceeded
51 Halted 0 ms 0 KB -