Submission #1261196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261196		patgra	Passport (JOI23_passport)	C++20	100 / 100	874 ms	209544 KiB

passport

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int inf = 1e8;

vector<vector<pair<int, int>>> g, gr;
vector<int> dist, distS, distT, distW;
int tB;
int n;

string iToS(int x) {
    string s;
    while(x) {
        s += (char)(x % 10 + '0');
        x /= 10;
    }
    if(s.empty()) return "0";
    ranges::reverse(s);
    return s;
}

string vToS(int v, bool xd) {
    if(v < tB) return "\"-" + iToS(v) + "-\"";
    if(v < 2 * tB) return (xd ? "\"\\\\" + iToS(v - tB) + "/\"" :"\"\\" + iToS(v - tB) + "/\"");
    if(v < 2 * tB + n) return (xd ? "\"/" + iToS(v - 2 * tB) + "\\\\\"" : "\"/" + iToS(v - 2 * tB) + "\\\"");
    if(v == 2 * tB + n) return "\"=S=\"";
    if(v == 2 * tB + n + 1) return "\"=T=\"";
    return "\"=W=\"";
}

void dijkstra(int start, bool rev) {
    DC << "dijkstra from " << vToS(start, 0) << eol;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    dist.resize(g.size(), inf);
    dist[start] = 0;
    q.push({0, start});
    while(q.size()) {
        auto [ds, v] = q.top();
        q.pop();
        if(ds > dist[v]) continue;
        repIn2(u, c, rev ? gr[v] : g[v]) if(dist[u] > ds + c) {
            dist[u] = ds + c, q.push({ds + c, u});
            DC << ' ' << vToS(u, 0) << " from " << vToS(v, 0) << " in " << ds + c << eol;
        }
    }
    DC << eol;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    tB = 1 << (32 - __builtin_clz(n - 1));
    g.resize(tB * 2 + n + 3);
    gr.resize(tB * 2 + n + 3);
    rep(i, 1, tB) g[i].pb({2 * i, 0}), g[i].pb({2 * i + 1, 0}), gr[2 * i].pb({i, 0}), gr[2 * i + 1].pb({i, 0});
    int l, r;
    rep(i, 0, n) {
        g[i + tB].pb({2 * tB + i, 1});
        gr[2 * tB + i].pb({i + tB, 1});
        cin >> l >> r;
        l += tB - 1, r += tB - 1;
        g[2 * tB + i].pb({l, 0});
        gr[l].pb({2 * tB + i, 0});
        if(r != l) {
        g[2 * tB + i].pb({r, 0});
        gr[r].pb({2 * tB + i, 0});
        }
        while(l / 2 != r / 2) {
            if(l % 2 == 0) g[2 * tB + i].pb({l + 1, 0}), gr[l + 1].pb({2 * tB + i, 0});
            if(r % 2 == 1) g[2 * tB + i].pb({r - 1, 0}), gr[r - 1].pb({2 * tB + i, 0});
            l /= 2; r /= 2;
        }
    }
    g[tB].pb({2 * tB + n, 0});
    gr[2 * tB + n].pb({tB, 0});
    g[tB + n - 1].pb({2 * tB + n + 1, 0});
    gr[2 * tB + n + 1].pb({tB + n - 1, 0});

    dijkstra(2 * tB + n, 1); swap(dist, distS);
    dijkstra(2 * tB + n + 1, 1); swap(dist, distT);

    rep(i, 0, 2 * tB + n + 2) {
        g[i].pb({2 * tB + n + 2, distS[i] + distT[i]});
        gr[2 * tB + n + 2].pb({i, distS[i] + distT[i]});
    }
    dijkstra(2 * tB + n + 2, 1); swap(dist, distW);
    
    DEBUG {
//        DC << "digraph {\n";
//        rep(i, 0, (int)g.size()) repIn2(u, c, g[i]) DC << " " << vToS(i) << " -> " << vToS(u) << " [weight=" << c * 10 << "]\n";
//        rep(i, 0, (int)g.size()) repIn2(u, c, g[i]) DC << " " << vToS(i) << " -> " << vToS(u) << "\n";
//        DC << "}" << eol;

        DC << "digraph { \n";
        rep(i, 1, 1) DC << ' ' << vToS(i, 1) << '\n';
//        rep(i, 0, (int)g.size()) repIn2(u, c, gr[i]) DC << " " << vToS(u) << " -> " << vToS(i) << " [weight=" << c << "]\n";
        rep(i, 0, (int)g.size()) repIn2(u, c, gr[i]) DC << " " << vToS(u, 1) << " -> " << vToS(i, 1) << "  \t// " << c << "\n";
        DC << "}" << eol << eol;

        DC << "distS: " << eol;
        rep(i, 0, (int)g.size()) DC << ' ' << vToS(i, 0) << ' ' << distS[i] << eol;
        DC << eol;
        DC << "distT: " << eol;
        rep(i, 0, (int)g.size()) DC << ' ' << vToS(i, 0) << ' ' << distT[i] << eol;
        DC << eol;
        DC << "distW: " << eol;
        rep(i, 0, (int)g.size()) DC << ' ' << vToS(i, 0) << ' ' << distW[i] << eol;
        DC << eol;
    }

    int q;
    cin >> q;
    rep(i, 0, q) {
        int x;
        cin >> x;
        x--;
        cout << (distW[tB + x] == inf ? -1 : distW[tB + x]) << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46