Submission #985565

#	Time	Username	Problem	Language	Result	Execution time	Memory
985565		maomao90	Spy 3 (JOI24_spy3)	C++17	100 / 100	53 ms	5892 KiB

Aoi

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "Aoi.h"
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 10005;
const int MAXM = 20005;
const int MAXK = 305;
const int LOGK = 9;
const int MAXQ = 16;
const int LOGQ = 4;

namespace {
    int n, m, q, k;
    ll c[MAXM];
    vii adj[MAXN];
    int subt[MAXN], tid[MAXN], bid[MAXM];
    ii p[MAXN];
    vii tree[MAXN];

    ll d[MAXN];
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    void dijkstra(int s) {
        REP (i, 0, n) {
            d[i] = LINF;
        }
        d[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [ud, u] = pq.top(); pq.pop();
            if (ud != d[u]) {
                continue;
            }
            for (auto [v, i] : adj[u]) {
                if (mnto(d[v], d[u] + c[i])) {
                    p[v] = {u, i};
                    pq.push({d[v], v});
                }
            }
        }
    }

    void root(int u) {
        for (auto [v, i] : tree[u]) {
            root(v);
            subt[u] += subt[v];
        }
    }
    vi badj[MAXK];
    vi bt[MAXK];
    vi stk;
    void dfs(int u) {
        if (tid[u] < q) {
            bt[stk.back()].pb(tid[u]);
        }
        for (auto [v, i] : tree[u]) {
            if (!subt[v]) {
                continue;
            }
            if (bid[i] < k) {
                badj[stk.back()].pb(bid[i]);
                stk.pb(bid[i]);
            }
            dfs(v);
            if (bid[i] < k) {
                stk.pop_back();
            }
        }
    }
    int bmnt[MAXK];
    void broot(int u) {
        bmnt[u] = INF;
        if (!bt[u].empty()) {
            sort(ALL(bt[u]));
            bmnt[u] = bt[u][0];
        }
        for (int v : badj[u]) {
            broot(v);
            mnto(bmnt[u], bmnt[v]);
        }
        sort(ALL(badj[u]), [&] (int l, int r) {
                return bmnt[l] < bmnt[r];
                });
    }
    int lptr;
    int tlabel[MAXQ + 5], blabel[MAXK];
    int ids[MAXQ + 5];
    int bdfs(int u) {
        int ptr = 0;
        int nxt = -1;
        blabel[u] = lptr;
        for (int v : badj[u]) {
            while (ptr < SZ(bt[u]) && bt[u][ptr] < bmnt[v]) {
                tlabel[nxt] = u;
                ids[lptr] = bt[u][ptr];
                nxt = bt[u][ptr++];
                lptr++;
            }
            tlabel[nxt] = u;
            nxt = bdfs(v);
        }
        while (ptr < SZ(bt[u])) {
            tlabel[nxt] = u;
            ids[lptr] = bt[u][ptr];
            nxt = bt[u][ptr++];
            lptr++;
        }
        return nxt;
    }

    vector<int> encode(int b, vector<int> k, vector<vector<int>> a) {
        assert(k.size() == a.size());
        int n = k.size();
        ld bits = 0;
        for (int i = 0; i < n; i++) {
            bits += a[i].size() * (log(k[i]) / log(b));
        }
        int m = ceil(bits);
        vector<int> x(m);
        for (int p = 0; p < m; p++) {
            int rem = 0;
            for (int i = n - 1; i >= 0; i--) {
                for (int j = a[i].size() - 1; j >= 0; j--) {
                    rem = rem * k[i] + a[i][j];
                    a[i][j] = rem / b;
                    rem %= b;
                }
            }
            x[p] = rem;
        }
        return x;
    }
}

string aoi(int N, int M, int Q, int K, vi A, vi B, vll C, vi T, vi X) {
    n = N; m = M; q = Q; k = K;
    REP (i, 0, m) {
        adj[A[i]].pb({B[i], i});
        adj[B[i]].pb({A[i], i});
        c[i] = C[i];
    }
    REP (i, 0, n) {
        tid[i] = INF;
    }
    REP (i, 0, q) {
        subt[T[i]] = 1;
        tid[T[i]] = i;
    }
    REP (i, 0, m) {
        bid[i] = INF;
    }
    REP (i, 0, k) {
        bid[X[i]] = i;
        blabel[i] = q;
    }
    dijkstra(0);
    REP (i, 1, n) {
        tree[p[i].FI].pb({i, p[i].SE});
    }
    root(0);
    stk.pb(k);
    dfs(0);
    broot(k);
    tlabel[bdfs(k)] = k;
    string s;
    assert(lptr <= q);
    vi tmp = encode(2, vi({q + 1, k + 1, q}), vector<vi>({vi(blabel, blabel + k), vi(tlabel, tlabel + q), vi(ids, ids + q)}));
    for (int i : tmp) {
        char c = i + '0';
        s += c;
    }
    return s;
}

Bitaro

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "Bitaro.h"
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 10005;
const int MAXM = 20005;
const int MAXK = 305;
const int LOGK = 9;
const int MAXQ = 16;
const int LOGQ = 4;

namespace {
    int n, m, q, k;
    string s;
    ll c[MAXM];
    vii adj[MAXN];
    int ids[MAXQ + 5];
    int blabel[MAXK], bid[MAXM];
    bool bvis[MAXK];
    int bl[MAXK];
    int tlabel[MAXQ + 5];
    bool tdone[MAXQ + 5];

    int qptr;
    ii p[MAXN], tp[MAXN];
    ll d[MAXN];
    priority_queue<pll, vector<pll>, greater<pll>> pq;

    vector<vector<int>> decode(int b, vector<int> k, vector<int> l, vector<int> x) {
        assert(k.size() == l.size());
        int n = k.size(), m = x.size();
        vector<vector<int>> a(n);
        for (int i = 0; i < n; i++) {
            a[i].resize(l[i]);
            for (int j = 0; j < l[i]; j++) {
                int rem = 0;
                for (int p = m - 1; p >= 0; p--) {
                    rem = rem * b + x[p];
                    x[p] = rem / k[i];
                    rem %= k[i];
                }
                a[i][j] = rem;
            }
        }
        return a;
    }
}

void bitaro(int N, int M, int Q, int K, vi A, vi B, vll C, vi T, vi X, string S) {
    s = S;
    n = N; m = M; q = Q; k = K;
    REP (i, 0, m) {
        adj[A[i]].pb({B[i], i});
        adj[B[i]].pb({A[i], i});
        c[i] = C[i];
    }
    REP (i, 0, k) {
        c[X[i]] = -1;
        bid[X[i]] = i;
    }
    vi vs;
    for (char c : s) {
        vs.pb(c - '0');
    }
    vector<vi> tmp = decode(2, vi({q + 1, k + 1, q}), vi({k, q, q}), vs);
    REP (i, 0, k) {
        blabel[i] = tmp[0][i];
    }
    REP (i, 0, q) {
        tlabel[i] = tmp[1][i];
    }
    REP (i, 0, q) {
        ids[i] = tmp[2][i];
    }
    REP (i, 0, n) {
        p[i] = {-1, -1};
    }
    vi bstk;
    bstk.pb(k);
    bvis[k] = 1;
    REP (l, 0, q) {
        int bu = bstk.back();
        int u = 0;
        if (bu < k) {
            u = p[A[X[bu]]].SE == X[bu] ? A[X[bu]] : B[X[bu]];
        }
        while (!pq.empty()) {
            pq.pop();
        }
        REP (i, 0, n) {
            d[i] = LINF;
        }
        d[u] = 0;
        pq.push({0, u});
        while (!pq.empty()) {
            auto [ud, u] = pq.top(); pq.pop();
            if (ud != d[u]) {
                continue;
            }
            for (auto [v, i] : adj[u]) {
                if (p[v].FI != -1 && p[v].FI != u) {
                    continue;
                }
                if (p[u].FI != -1 && p[u].FI == v) {
                    continue;
                }
                ll w = c[i];
                if (c[i] == -1) {
                    if (blabel[bid[i]] != l) {
                        continue;
                    }
                    w = 1;
                }
                if (mnto(d[v], ud + w)) {
                    if (c[i] == -1) {
                        bvis[bid[i]] = 1;
                        bl[bid[i]] = bl[bstk.back()] + 1;
                        bstk.pb(bid[i]);
                    }
                    tp[v] = {u, i};
                    pq.push({d[v], v});
                }
            }
        }
        int tid = ids[l];
        int tu = T[tid];
        while (tu != u) {
            p[tu] = tp[tu];
            tu = tp[tu].FI;
        }
        while (!bstk.empty() && bstk.back() != tlabel[tid]) {
            bvis[bstk.back()] = 0;
            bstk.pop_back();
        }
        assert(!bstk.empty());
    }
    REP (i, 0, q) {
        int u = T[i];
        vi e;
        while (u) {
            e.pb(p[u].SE);
            u = p[u].FI;
        }
        reverse(ALL(e));
        answer(e);
    }
}

Compilation message (stderr)

Bitaro.cpp:58:9: warning: '{anonymous}::qptr' defined but not used [-Wunused-variable]
   58 |     int qptr;
      |         ^~~~
Bitaro.cpp:56:10: warning: '{anonymous}::tdone' defined but not used [-Wunused-variable]
   56 |     bool tdone[MAXQ + 5];
      |          ^~~~~

• Subtask 1: 100 / 100