Submission #1215527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215527		mactoddlover	Passport (JOI23_passport)	C++17	100 / 100	424 ms	85944 KiB

passport

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 1e6 + 15;
const int INF = 1e9;

int n, q;
int leaf[N];
vector<pair<int,int>> g[N];
int fake_node[N];
int maxNode;
vector<pair<int,int>> multisource;

void build(int l, int r, int id){
    if(id >> 1) g[id].push_back({id >> 1, 0});// cout << id << " " << (id >> 1) << endl;
    if(l == r){
        leaf[l] = id;
        maximize(maxNode, id);
        return;
    }
    int mid = (l+r) >> 1;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1|1);
}

void add_edge(int l, int r, int id, int u, int v, int idx){
    if(r < u || l > v) return;
    if(u <= l && r <= v){
        //cout << id << "  " << fake_node[idx] << endl;
        g[id].push_back({fake_node[idx], 1});
        return;
    }
    int mid = (l+r) >> 1;
    add_edge(l,mid,id<<1,u,v,idx);
    add_edge(mid+1,r,id<<1|1,u,v,idx);
}

int dist[2][N]; // 0: 1, 1: n, 2: dist(y, 1) + dist(y, n);
int d[N];

void bfs01(int turn, int source){
    deque<int> dq;
    for(int i = 1; i <= maxNode; i++){
        d[i] = INF;
    }
    d[leaf[source]] = 0;
    dq.push_back(leaf[source]);
    while(!dq.empty()){
        int u = dq.front(); dq.pop_front();
        //cout << "case: " << u << endl;
        for(auto [v, w] : g[u]){
            //cout << v << endl;
            if(minimize(d[v], d[u] + w)){
                if(!w) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }

    for(int i = 1; i <= n; i++) dist[turn][i] = d[fake_node[i]];
}

void dijkstra(){
    for(int i = 1; i <= maxNode; i++){
        d[i] = INF;
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for(auto [u, w] : multisource){
        d[u] = w;
        pq.push(pii(w, u));
    }
    while(!pq.empty()){
        int u = pq.top().se, wu = pq.top().fi;
        pq.pop();
        if(d[u] < wu) continue;
        for(auto [v, wv] : g[u]){
            if(minimize(d[v], d[u] + wv)){
                pq.push(pii(d[v], v));
            }
        }
    }
}

void solve(){
    cin >> n;

    build(1,n,1);

    for(int i = 1; i <= n; i++){
        fake_node[i] = ++maxNode;
        g[fake_node[i]].push_back({leaf[i], 0});
    }

    for(int i = 1; i <= n; i++){
        int l, r; cin >> l >> r;
        add_edge(1,n,1,l,r,i);
    }

    bfs01(0,1);
    bfs01(1,n);

    for(int i = 1; i <= n; i++){
        //check if i can be a source -> can go to 1 and n
        // max(dist(i,1) , dist(i,n)) < INF
        // merge into dist(i,1) + dist(i,n) - 1 (buy passport only one time from source)
        if(max(dist[0][i], dist[1][i]) < INF){
            multisource.push_back({fake_node[i], dist[0][i] + dist[1][i] - 1});
        }
    }

    dijkstra();

    cin >> q;

    while(q--){
        int u; cin >> u;
        cout << (d[fake_node[u]] < INF ? d[fake_node[u]] : -1) << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

/*
    since L[i] <= i <= R[i] => create a segment [Li, Ri]
        1        [    (i)   ]      n
                      [  (i+1)]
                            [(i+2)  ]
       [            (i-1)]
    + consider node x:
        - if we can go from 1 -> x =>  cover all nodes from 1 -> x
        - if we can go from n -> x =>  cover all nodes from n -> x
        - an optimize path from x to 1 and n will looks like this:

                x ---> y ----> 1
                       |
                       |
                       n
        - break into 3 parts dist(x, y) + dist(y, n) + dist(y, 1)
        - dist(y, n) + dist(y, 1) : use bfs01
        - dist(x, y) + (dist(y, n) + dist(y, 1)): dijkstra
*/

Compilation message (stderr)

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

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