Submission #1258507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258507		CrabCNH	Passport (JOI23_passport)	C++20	46 / 100	500 ms	84924 KiB

passport

#include <bits/stdc++.h>

#define task     "BriantheCrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}

const int maxN = 4e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

// khong tu code thi khong kha len duoc dau
// biet sol roi thi tu lam not di

int n;
pii a[maxN];
vector <int> adj[maxN * 4];
bool visited[maxN * 4];

void upd (int id, int l, int r, int u, int v, int val) {
    if (v < l || u > r) {
        return;
    }
    if (u <= l && r <= v) {
        adj[id].push_back (val);
        return;
    }
    int mid = (l + r) >> 1;
    upd (id * 2, l, mid, u, v, val);
    upd (id * 2 + 1, mid + 1, r, u, v, val);
}

void dijkstra (int st, vector <int> &d) {
    for (int i = 0; i <= n * 4; i ++) {
        visited[i] = 0;
    }
    priority_queue <pii, vector <pii>, greater <pii>> pq;
    if (st != -1) {
        d[st] = 0;
        pq.push ({d[st], st});
    }
    else {
        for (int i = 1; i <= n; i ++) {
            if (d[i] != inf) {
                pq.push ({d[i], i});
            }
        }
    }
    while (!pq.empty ()) {
        auto [c, u] = pq.top ();
        pq.pop ();
        if (c > d[u]) {
            continue;
        }
        int id = 1, l = 1, r = n;
        while (true) {
            if (visited[id] == 0) {
                visited[id] = 1;
                for (auto v : adj[id]) {
                    if (d[v] > d[u] + 1) {
                        d[v] = d[u] + 1;
                        pq.push ({d[v], v});
                    }
                }
            }
            if (l == r) {
                break;
            }
            int mid = (l + r) >> 1;
            if (u <= mid) {
                id = id * 2;
                r = mid;
            }
            else {
                id = id * 2 + 1;
                l = mid + 1;
            }
        }
    }
    
}

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int l, r;
        cin >> l >> r;
        a[i] = {l, r};
        upd (1, 1, n, l, r, i);
    }
    vector <int> d1 (n + 2, inf);
    vector <int> dn (n + 2, inf);
    dijkstra (1, d1);
    dijkstra (n, dn);
    vector <int> db (n + 2, inf);
    for(int i = 1; i <= n; i ++){
        db[i] = d1[i] + dn[i];
        if (i != 1 && i != n) {
            db[i] --;
        }
        if (a[i].fi == 1 && a[i].se == n) {
            db[i] = 1;
        }
    }
    dijkstra (-1, db);
    int q;
    cin >> q;
    while (q --) {
        int x;
        cin >> x;
        cout << (db[x] == inf ? -1 : db[x]) << '\n';
    }
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfv

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:133:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:134:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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