Submission #1221973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221973		wiwiho	Game (APIO22_game)	C++17	0 / 100	0 ms	412 KiB

game

#include "game.h"

#include <bits/stdc++.h>
using namespace std;

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb emplace_back
#define ff first
#define ss second
#define SZ(a) int(a.size())

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef zisk
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.ff << ',' << p.ss << ')';
}

#define lc 2 * id
#define rc 2 * id + 1
namespace {

    int n, k;
    vector<pii> seg;
    vector<int> pos;
    vector<vector<int>> g, rev;
    vector<int> vst;

    int query(int ql, int qr, int L = -1, int R = k, int id = 1) {
        int M = L + (R - L) / 2;
        if (L == R) return id;
        if (ql <= M && M < qr) return id;
        if (qr <= M) return query(ql, qr, L, M, lc);
        else return query(ql, qr, M + 1, R, rc);
    }
    void push_node(int v, int l, int r) {
        int id = pos[v];
        l = max(l, seg[id].ff);
        r = min(r, seg[id].ss);
        pos[v] = query(l, r, seg[id].ff, seg[id].ss, id);
    }

    int get_come(int v) {
        int id = pos[v];
        if (seg[id].ff == seg[id].ss) return id;
        return lc;
    }
    int get_go(int v) {
        int id = pos[v];
        if (seg[id].ff == seg[id].ss) return id;
        return rc;
    }
    bool isAnc(int a, int b) {
        return seg[a].ff <= seg[b].ff && seg[b].ss <= seg[a].ss;
    }

    void add_edge(int u, int v) {
        g[u].pb(v);
        rev[v].pb(u);
    }

}

void init(int _n, int _k) {
    n = _n;
    k = _k;

    seg.resize(4 * (k + 2));
    pos.resize(n);
    g.resize(n); rev.resize(n);
    vst.resize(n);
    for (int i = 0; i < k - 1; i++)
        add_edge(i, i + 1);
    auto build = [&](auto dfs, int l, int r, int id) -> void {
        debug("build", l, r, id);
        seg[id] = pii(l, r);
        if (l == r) return;
        int m = l + (r - l) / 2;
        dfs(dfs, l, m, lc);
        dfs(dfs, m + 1, r, rc);
    };
    build(build, -1, k, 1);
    debug("ok");
    for (int i = 0; i < n; i++) {
        if (i < k) pos[i] = query(i, i);
        else pos[i] = 1;
    }
    debug("init done");

}

int add_teleporter(int u, int v) {
    debug("test", u, v);
    add_edge(u, v);

    int come = u, go = v;
    bool flag = false;

    auto comp_come = [&](int x, int y) {
        x = get_come(x); y = get_come(y);
        if (x == y) return false;
        if (isAnc(x, y)) return false;
        if (isAnc(y, x)) return true;
        return !(seg[x].ss < seg[y].ff);
    };
    auto comp_go = [&](int x, int y) {
        x = get_go(x); y = get_go(y);
        if (x == y) return false;
        if (isAnc(x, y)) return false;
        if (isAnc(y, x)) return true;
        return !(seg[y].ss < seg[x].ff);
    };

    priority_queue<int, vector<int>, decltype(comp_come)> come_pq(comp_come);
    priority_queue<int, vector<int>, decltype(comp_go)> go_pq(comp_go);

    auto relax_come = [&](int p) {
        debug("relax_come", p);
        if (seg[get_come(p)].ss < seg[get_come(come)].ff) return;
        if (seg[get_come(p)].ss < seg[get_go(go)].ff) return;
        if (seg[get_go(go)].ss <= seg[get_come(p)].ff) {
            flag = true;
            return;
        }
        if (comp_come(come, p)) come = p;
        come_pq.push(p);
    };
    auto relax_go = [&](int p) {
        debug("relax_go", p);
        if (seg[get_go(go)].ss < seg[get_go(p)].ff) return;
        if (seg[get_come(come)].ss < seg[get_go(p)].ff) return;
        if (seg[get_go(p)].ss <= seg[get_come(come)].ff) {
            flag = true;
            return;
        }
        if (comp_go(go, p)) go = p;
        go_pq.push(p);
    };

    relax_come(u);
    relax_go(v);

    vector<int> todo_come;
    vector<int> todo_go;
    debug("ok");

    while (!flag) {
        debug("gao", come, seg[pos[come]], go, seg[pos[go]]);
        if (seg[get_come(come)].ss < seg[get_go(go)].ff) break;
        if (seg[get_go(go)].ss <= seg[get_come(come)].ff)
            return 1;

        assert(isAnc(get_come(come), get_go(go)) || 
                isAnc(get_go(go), get_come(come)));

        if (isAnc(get_come(come), get_go(go))) {
            debug("come");
            assert(!come_pq.empty());
            int now = come_pq.top();
            come_pq.pop();
            if (seg[get_come(now)].ss < seg[get_come(come)].ff) continue;
            push_node(now, -1, seg[get_go(go)].ss);
            todo_come.pb(now);
            for (int i : rev[now])
                relax_come(i);
        }
        else {
            debug("go");
            assert(!go_pq.empty());
            int now = go_pq.top();
            go_pq.pop();
            if (seg[get_go(go)].ss < seg[get_go(now)].ff) continue;
            push_node(now, seg[get_come(come)].ff, k);
            todo_go.pb(now);
            for (int i : g[now])
                relax_go(i);
        }
    }
    
    reverse(iter(todo_come));
    reverse(iter(todo_go));

    for (int now : todo_come) {
        push_node(now, -1, seg[get_go(go)].ss);
        for (int i : g[now])
            push_node(i, seg[get_come(now)].ff, k);
    }
    for (int now : todo_go) {
        push_node(now, seg[get_come(come)].ff, k);
        for (int i : rev[now])
            push_node(i, -1, seg[get_go(now)].ss);
    }
    
    if (flag) return 1;
    if (seg[get_come(come)].ss < seg[get_go(go)].ff) return 0;
    if (seg[get_go(go)].ss <= seg[get_come(come)].ff) return 1;
    return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40