Submission #1258472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258472		khoile08	Passport (JOI23_passport)	C++17	100 / 100	235 ms	28160 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define lcm(a,b) a / __gcd(a, b) * b
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int n, k;

struct Ticket {
    int c, p, a, b;
    bool operator < (const Ticket &other) const {return a < other.a;}
};
Ticket a[N];

ll d[4][2 * N];

struct Smt {
    int seg[4 * N];

    void build(int id, int l, int r) {
        if(l == r) {
            seg[id] = a[l].b;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
    }

    void del(int id, int l, int r, int x, vector<int> &node) {
        if(l > r || x < a[l].a || x > seg[id]) return;
        if(l == r) {
            node.pb(l);
            seg[id] = -1;
            return;
        }
        int mid = (l + r) >> 1;
        del(id << 1, l, mid, x, node);
        del(id << 1 | 1, mid + 1, r, x, node);
        seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
    }
};
Smt it;

void Dijkstra(int sr, ll d[]) {
    priority_queue<ii,vector<ii>,greater<ii>> pq;
    if(sr) {
        pq.push({0, sr});
        FOR(i, 1, n + k) d[i] = INF;
        d[sr] = 0;
    }
    else {
        FOR(i, 1, k) d[a[i].c] = min(d[a[i].c], d[i + n] + a[i].p);
        FOR(i, 1, n) if(d[i] < INF) pq.push({d[i], i});
    }

    while(!pq.empty()) {
        ll cost = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if(cost != d[u]) continue;
        vector<int> node;
        it.del(1, 1, k, u, node);
        for(int v : node) {
            if(d[v + n] > cost) {
                d[v + n] = cost;
                if(d[a[v].c] > cost + a[v].p) {
                    d[a[v].c] = cost + a[v].p;
                    pq.push({d[a[v].c], a[v].c});
                }
            }
        }
    }
}

void Solve() {
    sort(a + 1, a + 1 + k);
    it.build(1, 1, k);
    Dijkstra(1, d[1]);
    it.build(1, 1, k);
    Dijkstra(n, d[2]);
    FOR(i, 1, n + k) {
        if(d[2][i] < INF && d[1][i] < INF) d[3][i] = d[2][i] + d[1][i];
        else d[3][i] = INF;
    }
    it.build(1, 1, k);
    Dijkstra(0, d[3]);
    int q;
    cin >> q;
    FOR(i, 1, q) {
        int x;
        cin >> x;
        cout << (d[3][x] == INF ? -1 : d[3][x]) << '\n';
    }
}

signed main() {
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int test = 1;
//    cin >> test;
    while(test--) {
        cin >> n;
        k = n;
        FOR(i, 1, k) {
            cin >> a[i].a >> a[i].b;
            a[i].p = 1;
            a[i].c = i;
        }
        Solve();
    }
}

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