Submission #1261654

#TimeUsernameProblemLanguageResultExecution timeMemory
1261654Szymon_PilipczukPassport (JOI23_passport)C++20
6 / 100
582 ms91936 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define st first #define nd second #define pb push_back #define all(a) a.begin(),a.end() #define rep(a,b) for(int a = 0;a<b;a++) const int inf = 1e9; const ll infl = 1e18; vector<vector<pair<int,int>>> gr; pair<int,int> b[200000]; int n; void add(int l,int r,int p) { p+=n; l+=n; r+=n; gr[l].pb({p,1}); if(l!=r)gr[r].pb({p,1}); while(l/2 != r/2) { if(l%2==0)gr[l+1].pb({p,1}); if(r%2==1)gr[r-1].pb({p,1}); l/=2;r/=2; } } int dis[400002][2]; int tdis[400001]; priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq; void dk(int c,int p,bool m) { //cerr<<c<<" "<<p<<" "<<m<<"\n"; for(pair<int,int> i : gr[p]) { //cerr<<i.st<<" "<<i.nd<<"\n"; if(c + i.nd < dis[i.st][m]) { dis[i.st][m] = c + i.nd; pq.push({c+i.nd,i.st,m}); } } } priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq2; void dk2(int c,int p) { //cerr<<c<<" "<<p<<"\n"; for(pair<int,int> i : gr[p]) { if(c + i.nd < tdis[i.st]) { tdis[i.st] = c + i.nd; pq2.push({c+i.nd,i.st}); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; gr.resize(2*n+2); rep(i,n) { cin>>b[i].st>>b[i].nd; b[i].st--;b[i].nd--; add(b[i].st,b[i].nd,i); } gr[n*2].pb({n,0}); gr[n*2+1].pb({2*n-1,0}); for(int i = n*2-1;i>1;i--) { gr[i].pb({i/2,0}); } rep(i,n*2+2) { dis[i][0] = inf; dis[i][1] = inf; } dis[n*2][0] = 0; dis[n*2+1][1] = 0; pq.push({0,n*2,0}); pq.push({0,n*2+1,1}); while(!pq.empty()) { vector<int> cc = pq.top(); pq.pop(); if(dis[cc[1]][cc[2]] == cc[0])dk(cc[0],cc[1],cc[2]); } //cerr<<"\n"; gr.pop_back(); gr.pop_back(); gr.pb({}); //cerr<<dis[7][0]<<" "<<dis[7][1]<<"\n"; for(int i = 1;i<2*n;i++) { gr[n*2].pb({i,dis[i][0] + dis[i][1]}); } rep(i,n) { if(b[i].st == 0 && b[i].nd == n-1) { gr[n*2].pb({i+n,1}); } } rep(i,n*2) { tdis[i] = inf; } pq2.push({0,n*2}); while(!pq2.empty()) { pair<int,int> cc = pq2.top(); pq2.pop(); if(tdis[cc.nd] == cc.st)dk2(cc.st,cc.nd); } // cerr<<tdis[6]<<"\n"; int q; cin>>q; rep(i,q) { int p; cin>>p; p--; if(tdis[p+n] >= inf) { cout<<-1<<"\n"; } else { cout<<tdis[p+n]<<"\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...