제출 #1306455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306455		Bahamin	Passport (JOI23_passport)	C++20	100 / 100	524 ms	90424 KiB

passport

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const int MAX_N = 2e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

vector<pair<int, int>> adj[MAX_N << 2];
int ind[MAX_N];
int cnt = 0;

void build(int l, int r, int id)
{
    cnt = max(cnt, id);
    if (l == r - 1) 
    {
        ind[l] = id;
        return;
    }
    build(l, mid, lid);
    build(mid, r, rid);
    adj[lid].push_back({id, 0}); adj[rid].push_back({id, 0});
}

void add(int s, int t, int x, int l, int r, int id)
{
    if (s <= l && t >= r)
    {
        adj[id].push_back({x, 0});
        return;
    }
    if (s >= r || t <= l) return;
    if (s < mid) add(s, t, x, l, mid, lid);
    if (t > mid) add(s, t, x, mid, r, rid);
}

int dis[3][MAX_N << 2];

void bfs(int u, int x)
{
    fill(dis[x], dis[x] + (MAX_N << 2), INF);
    dis[x][u] = 0;
    deque<int> dq;
    dq.push_back(u);
    while (dq.size())
    {
        int u = dq.back();
        dq.pop_back();
        // cout << u << " " << dis[x][u] << endl;
        for (auto v : adj[u]) if (dis[x][v.first] > dis[x][u] + v.second) 
        {
            dis[x][v.first] = dis[x][u] + v.second;
            if (v.second) dq.push_front(v.first);
            else dq.push_back(v.first);
        }
    }
}

void djk()
{
    fill(dis[2], dis[2] + (MAX_N << 2), INF);
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < (MAX_N << 2); i++) pq.push({-(dis[0][i] + dis[1][i]), i}), dis[2][i] = dis[0][i] + dis[1][i];
    while (pq.size())
    {
        auto x = pq.top();
        pq.pop();
        if (-x.first != dis[2][x.second]) continue;
        // cout << x << endl;
        for (auto v : adj[x.second]) if (dis[2][v.first] > -x.first + v.second)
        {
            dis[2][v.first] = -x.first + v.second;
            pq.push({-dis[2][v.first], v.first});
        }
    }
}

void solve() {
    int n;
    cin >> n;
    build(0, n, 1);
    for (int i = 0; i < n; i++) adj[cnt + i + 1].push_back({ind[i], 1});
    for (int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        add(l - 1, r, cnt + i + 1, 0, n, 1);
    }  
    // cout << "oh" << endl;
    bfs(ind[0], 0); bfs(ind[n - 1], 1);
    djk();
    int q;
    cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        if (dis[2][ind[x - 1]] >= INF) cout << -1 << "\n";
        else cout << dis[2][ind[x - 1]] << "\n";
    }
}   

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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