Submission #1251682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251682		mngoc._.	Passport (JOI23_passport)	C++20	100 / 100	691 ms	141004 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOD(i, r, l) for (int i = (r), _l = (l); i >= _l; i--)
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define Konosuba tuple<int , int , int, int>
#define fi first
#define se second


const int N = 3e5 + 5;
const int MOD = 1e9 + 7;
const int block = 330;
const int LOG = 30;
const int MAXN = 1e6 + 1;
const int INF = 1e14;
const int base = 311;


template<class A, class B>
bool umin(A& var, const B& val){ return (val < var) ? (var = val, true) : false; }
template<class A, class B>
bool umax(A& var, const B& val){ return (var < val) ? (var = val, true) : false; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> int random(const int& l, const int& r) {
  return uniform_int_distribution<int>(l,r)(rng);
}

int n;
int IdxOnSeg[N];
pii a[N];
vector<pii> adj[4 * N + 1];
int dist[4 * N + 1][3];

void dijikstra(int u , int type){
	FOR(i , 1 , 4 * n + 1){
		dist[i][type] = INF;
	}
	dist[u][type] = 0;
	priority_queue<pii , vector<pii> , greater<pii>> pq;
	pq.push(make_pair(dist[u][type] , u));
	while(pq.size()){
		int val = pq.top().first;
		int tmpu = pq.top().second;
		pq.pop();
		if(val > dist[tmpu][type]) continue;
		for(auto v : adj[tmpu]){
		    if(dist[v.first][type] > dist[tmpu][type] + v.second){
		    	 dist[v.first][type] = dist[tmpu][type] + v.second;
		    	 pq.push({dist[v.first][type] , v.first});
			}
		}
	}
	
	
}

void dijikstra2(void){
	priority_queue<pii , vector<pii> , greater<pii>> pq;
	FOR(i , 1 , n){
	    pq.push(make_pair(dist[IdxOnSeg[i]][2] , IdxOnSeg[i]));
	}
	while(pq.size()){
		int val = pq.top().first;
		int tmpu = pq.top().second;
		pq.pop();
		if(val > dist[tmpu][2]) continue;
		for(auto v : adj[tmpu]){
		    if(dist[v.first][2] > dist[tmpu][2] + v.second){
		    	 dist[v.first][2] = dist[tmpu][2] + v.second;
		    	 pq.push({dist[v.first][2] , v.first});
			}
		}
	}
	
	
}

void build(int idx , int l , int r){
	if(l == r){
		IdxOnSeg[l] = idx;
		return; 
	}
	int mid = (l + r) / 2;
	build(2 * idx , l , mid);
	build(2 * idx + 1 , mid + 1 , r);
	adj[2 * idx].push_back(make_pair(idx , 0));
	adj[2 * idx + 1].push_back(make_pair(idx , 0));
}

void get(int idx,  int l , int r , int u , int v , int pos){
	if(l > v || r < u) return;
	if(u <= l && r <= v){
		adj[idx].push_back(make_pair(pos , 1));
		return;
	}
	int mid = (l + r) / 2;
	get(2 * idx , l , mid , u , v , pos);
	get(2 * idx + 1 , mid + 1 , r , u , v ,pos);
}



void solve(void){
	cin >> n;
	build(1 , 1 , n);

	FOR(i , 1 , n){
		cin >> a[i].first >> a[i].second;
	}
	FOR(i , 1 , n){
		get(1 , 1 , n , a[i].first , a[i].second , IdxOnSeg[i]);
	}

	
	dijikstra(IdxOnSeg[1] , 0);
	dijikstra(IdxOnSeg[n] , 1);
	
	FOR(i , 1 , 4 * n + 1){
		dist[i][2] = INF;
	}
	FOR(i , 1 , n){
		dist[IdxOnSeg[i]][2] = dist[IdxOnSeg[i]][1] + dist[IdxOnSeg[i]][0];
		if(i != 1 && i != n) dist[IdxOnSeg[i]][2] --;
		
	}
	dijikstra2();
	int q; cin >> q;
	FOR(i , 1 , q){
		int x; cin >> x;
		if(dist[IdxOnSeg[x]][2] >= INF / 2) cout << -1 << endl;
		else cout << dist[IdxOnSeg[x]][2] << endl;
	}
	
	
	
	
	
		
}




signed main(void) {
    if (fopen("smod.INP", "r")) {
        freopen("smod.INP", "r", stdin);
        freopen("smod.OUT", "w", stdout);
    } 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCase = 1; //cin >> testCase;
    FOR(i , 1 , testCase){
        solve();
    }

    cerr << "Time elapsed: " << TIME << "s.\n";
    return (0);
}

Compilation message (stderr)

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

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