Submission #966740

#	Time	Username	Problem	Language	Result	Execution time	Memory
966740		Nhoksocqt1	Game (APIO22_game)	C++17	60 / 100	4057 ms	51312 KiB

game

#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 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 0 / 40