Submission #737633

#	Time	Username	Problem	Language	Result	Execution time	Memory
737633		He_Huanglu	Passport (JOI23_passport)	C++17	100 / 100	925 ms	98152 KiB

passport

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 3e5 + 5;
int n, nq, d[4 * N][2], f[4 * N], id[N];
bool ok[4 * N];
vector <ii> ke[4 * N];

void build(int i, int l, int r) {
    if(l == r) {
        id[l] = i;
        ok[i] = 1;
        return ;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    ke[i << 1].push_back({i, 0});
    ke[i << 1 | 1].push_back({i, 0});
}

void join(int x, int i, int l, int r, int u, int v) {
    if(l > v || u > r) return ;
    if(u <= l && r <= v) {
        if(id[x] != i) ke[i].push_back({id[x], 1});
        return ;
    }
    int mid = l + r >> 1;
    join(x, i << 1, l, mid, u, v);
    join(x, i << 1 | 1, mid + 1, r, u, v);
}

void dij(int x, int j) {
    priority_queue <ii, vector <ii>, greater <ii> > pq;
    d[x][j] = 0;
    pq.push({d[x][j], x});
    while (!pq.empty()) {
        ii e = pq.top();
        pq.pop();
        if(e.fi != d[e.se][j]) continue;
        for(auto [v, w] : ke[e.se]) if(d[v][j] > e.fi + w) {
            d[v][j] = e.fi + w;
            pq.push({d[v][j], v});
        }
    }
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
        join(i, 1, 1, n, l, r);
    }
    memset(d, 60, sizeof d);
    dij(id[1], 0);
    dij(id[n], 1);
    priority_queue <ii, vector <ii>, greater <ii> > pq;
    for(int i = 1; i <= 4 * n; i++) {
        f[i] = d[i][0] + d[i][1] - ((i == id[1] || i == id[n]) ? 0 : ok[i]);
        pq.push({f[i], i});
    }
    while (!pq.empty()) {
        ii e = pq.top();
        pq.pop();
        if(e.fi != f[e.se]) continue;
        for(auto [v, w] : ke[e.se]) if(f[v] > e.fi + w) {
            f[v] = e.fi + w;
            pq.push({f[v], v});
        }
    }
    cin >> nq;
    for(int i = 1; i <= nq; i++) {
        int x; cin >> x;
        x = id[x];
        cout << (f[x] > n ? -1 : f[x]) << "\n";
    }
    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'void join(int, int, int, int, int, int)':
passport.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: At global scope:
passport.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main () {
      | ^~~~
passport.cpp: In function 'int main()':
passport.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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