Submission #878477

#	Time	Username	Problem	Language	Result	Execution time	Memory
878477		prohacker	Passport (JOI23_passport)	C++14	48 / 100	2053 ms	172764 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[3][8*N];
vector<pii> adj[16*N];
int idx[2][8*N],ok[16*N];
int q;

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

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

queue<int> pq;

void dijkstra(int d[]) {
    while(!pq.empty()) {
        int u = pq.front();
        pq.pop();
        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(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 = 2*n;
    build();
    for(int i = 1 ; i <= n ; i++) {
        int l,r; cin >> l >> r;
        update(i+n,l,r,1);
        adj[i+n].push_back({i,0});
    }
    for(int j = 0 ; j < 3 ; j++) {
        for(int i = 1 ; i <= cnt ; i++) {
            d[j][i] = 1e8;
        }
    }
    d[0][1] = 0;
    pq.push(1);
    dijkstra(d[0]);
    d[1][n] = 0;
    pq.push(n);
    dijkstra(d[1]);
    for(int i = 1 ; i <= cnt ; i++) {
        if(i == 1 or i == n) {
            d[2][i] = d[0][i] + d[1][i];
        }
        else {
            if(1 <= i and i <= n) {
                d[2][i] = d[0][i] + d[1][i] - 1;
            }
            else {
                d[2][i] = d[0][i] + d[1][i];
            }
        }
        pq.push(i);
    }
    dijkstra(d[2]);
    cin >> q;
    while(q--) {
        int x; cin >> x;
        if(d[2][x] >= 1e8) {
            d[2][x] = -1;
        }
        cout << d[2][x] << '\n';
    }
    return 0;
}

Compilation message (stderr)

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

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