Submission #878498

#	Time	Username	Problem	Language	Result	Execution time	Memory
878498		prohacker	Passport (JOI23_passport)	C++14	100 / 100	600 ms	83484 KiB

passport

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>

using namespace std;

const int N = 2e5+10;
const int INF = INT_MAX;
const int mod = 1e9+7;
const string NAME = "solve";

int n,cnt;
int d[2][4*N];
vector<pii> adj[4*N];
int idx[4*N];
int q;

void build(int id = 1, int l = 1, int r = n) {
    if(l == r) {
        idx[id] = l;
        return;
    }
    idx[id] = ++cnt;
    int mid = l + r >> 1;
    build(id << 1,l,mid);
    build(id << 1 | 1,mid+1,r);
    adj[idx[id << 1]].push_back({idx[id],0});
    adj[idx[id << 1 | 1]].push_back({idx[id],0});
}

void update(int root, int u, int v, int id = 1, int l = 1, int r = n) {
    if(u <= l and r <= v) {
        adj[idx[id]].push_back({root,1});
        return;
    }
    int mid = l + r >> 1;
    if(u <= mid) {
        update(root,u,v,id << 1,l,mid);
    }
    if(mid+1 <= v) {
        update(root,u,v,id << 1 | 1,mid+1,r);
    }
}

priority_queue<pii,vector<pii>,greater<pii>> pq;

void dijkstra(int d[]) {
    while(!pq.empty()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();
        if(du > d[u]) {
            continue;
        }
        for(auto p:adj[u]) {
            int v = p.first;
            int w = p.second;
            if(d[u] + w < d[v]) {
                d[v] = d[u] + w;
                pq.push({d[v],v});
            }
        }
    }
}

signed main()
{
    if (fopen((NAME + ".inp").c_str(), "r")) {
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cnt = n;
    build();
    for(int i = 1 ; i <= n ; i++) {
        int l,r; cin >> l >> r;
        update(i,l,r);
    }
    for(int j = 0 ; j < 2 ; j++) {
        for(int i = 1 ; i <= cnt ; i++) {
            d[j][i] = 1e8;
        }
    }
    d[0][1] = 0;
    pq.push({0,1});
    dijkstra(d[0]);
    d[1][n] = 0;
    pq.push({0,n});
    dijkstra(d[1]);
    for(int i = 1 ; i <= cnt ; i++) {
        d[0][i] = d[0][i] + d[1][i];
        if(1 < i and i < n) {
            d[0][i]--;
        }
        pq.push({d[0][i],i});
    }
    dijkstra(d[0]);
    cin >> q;
    while(q--) {
        int x; cin >> x;
        if(d[0][x] >= 1e8) {
            d[0][x] = -1;
        }
        cout << d[0][x] << '\n';
    }
    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'void update(int, int, int, int, int, int)':
passport.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'int main()':
passport.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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