Submission #1258078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258078		Bui_Quoc_Cuong	Passport (JOI23_passport)	C++20	48 / 100	416 ms	178952 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define fi first
#define se second
const int N = 6E5 + 5;

int n, q;
int L[N], R[N];

int base, LIM, ID[N];
vector <pair <int, int>> g[8 * N];

void pushDown(int id, int l, int r) {
    if (l == r) {
        ID[l] = id;
        base = max(base, id);
        return;
    }
    int mid = (l + r) >> 1;
    g[id].push_back(make_pair(id << 1, 0));
    g[id].push_back(make_pair(id << 1 | 1, 0));
    pushDown(id << 1, l, mid);
    pushDown(id << 1 | 1, mid + 1, r);
}
 
void pushUp(int id, int l, int r) {
    if (l == r) {
        g[id + base].push_back(make_pair(id, 0));
        g[id].push_back(make_pair(id + base, 0));
        LIM = max(LIM, id + base);
        return;
    }
    int mid = (l + r) >> 1;
    g[id * 2 + base].push_back(make_pair(id + base, 0));    
    g[id * 2 + 1 + base].push_back(make_pair(id + base, 0));
    pushUp(id << 1, l, mid);
    pushUp(id << 1 | 1, mid + 1, r);
}
 
void addEdge(int id, int l, int r, int u, int v, int root, int w, int type) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {     
        if (type == 1 || type == 3) {
            g[id + base].push_back(make_pair(ID[root], w));
        } else {
            g[ID[root]].push_back(make_pair(id, w));
        }
        return;
    }
    int mid = (l + r) >> 1;
    addEdge(id << 1, l, mid, u, v, root, w, type);
    addEdge(id << 1 | 1, mid + 1, r, u, v, root, w, type);
}

long long dist1[N], distn[N], dist[N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #define ko "kieuoanh"
    if (fopen(ko".inp", "r")) {
        freopen(ko".inp", "r", stdin); freopen(ko".out", "w", stdout);
    }
    cin >> n;
    FOR(i, 1, n) cin >> L[i] >> R[i];
    cin >> q;
    
    pushDown(1, 1, n);
    pushUp(1, 1, n);
    FOR(i, 1, n) addEdge(1, 1, n, L[i], R[i], i, 1, 1);

    auto dijkstra = [&] (int st, long long dist[]) {
        FOR(i, 1, LIM) dist[i] = 1e18;
        
        #define bg array <long long, 2>
        priority_queue <bg, vector <bg>, greater <bg>> pq;
        pq.push({dist[ID[st]] = 0, ID[st]});

        while (!pq.empty()) {
            int u = pq.top()[1]; 
            long long cost = pq.top()[0];
            pq.pop();
            if (cost > dist[u]) continue;
            for (pair <int, int> &it : g[u]) {
                int v = it.first, w = it.second;
                if (dist[v] > cost + w) {
                    dist[v] = cost + w;
                    pq.push({dist[v], v});
                }
            }
        }
    };

    dijkstra(1, dist1);
    dijkstra(n, distn);

    FOR(i, 1, LIM) dist[i] = 1e18;
    #define bg array <long long, 2>
    priority_queue <bg, vector <bg>, greater <bg>> pq;

    FOR(i, 1, n) {
        if (dist1[ID[i]] == 1e18) continue;
        if (distn[ID[i]] == 1e18) continue;
        long long cost = dist1[ID[i]] + distn[ID[i]] - (i != 1 && i != n);
        pq.push({dist[ID[i]] = cost, ID[i]});
    }

    while (!pq.empty()) {
        int u = pq.top()[1]; 
        long long cost = pq.top()[0];
        pq.pop();
        if (cost > dist[u]) continue;
        for (pair <int, int> &it : g[u]) {
            int v = it.first, w = it.second;
            if (dist[v] > cost + w) {
                dist[v] = cost + w;
                pq.push({dist[v], v});
            }
        }
    }

    while (q--) {
        int u; cin >> u;
        cout << (dist[ID[u]] >= 1e18 ? - 1 : dist[ID[u]]) << "\n";
    }

    return 0;
}

Compilation message (stderr)

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

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