Submission #728049

#	Time	Username	Problem	Language	Result	Execution time	Memory
728049		MohammadAghil	Passport (JOI23_passport)	C++17	100 / 100	1172 ms	157888 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)size(x)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<ll, ll> pp;

void dbg(){
     cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          // freopen("inp.txt", "r", stdin);
          // freopen("out.txt", "w", stdout);
          #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
     #else
          #define er(...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7, maxn = 8e5 + 5, lg = 21, inf = ll(1e18) + 5;

vector<pp> adj[maxn];
int n, t;
ll dist[3][maxn];

void build(){
     rep(i,2,n<<1){
          adj[i+t].pb({(i>>1)+t, 0});
     }
     rep(i,n,n<<1){
          adj[i-n].pb({i+t, 0});
     }
}

void addEdge(int i, int l, int r, int w){
     for(l += n, r += n; l < r; l >>= 1, r >>= 1){
          if(l&1) adj[l+t].pb({i, w}), l++;
          if(r&1) r--, adj[r+t].pb({i, w});
     }
}

void dij(ll* dist, int st){
     priority_queue<pp, vector<pp>, greater<pp>> q;
     if(st == -1){
          rep(i,0,maxn) q.push({dist[i], i}); 
     } else{
          fill(dist, dist + maxn, inf);
          q.push({dist[st] = 0, st});
     }
     while(sz(q)){
          auto[w, r] = q.top(); q.pop();
          if(w - dist[r] || w >= inf) continue; 
          for(auto[c, d]: adj[r]) if(dist[c] > w + d){
               q.push({dist[c] = w + d, c});
          }
     }
}

int P[maxn];

int main(){ IOS();
     cin >> n;
     t = n<<1;
     build();
     fill(dist[2], dist[2] + maxn, inf);
     rep(i,0,n){
          int a, b; cin >> a >> b; a--;
          adj[i + n].pb({i, 0});
          adj[i].pb({i + n, 1});
          addEdge(i + n, a, b, 1);
     }
     dij(dist[0], 0);
     dij(dist[1], n-1);
     rep(i,n,t){
          dist[2][i] = dist[0][i] + dist[1][i] - 1;
     }
     dij(dist[2], -1);
     int q; cin >> q;
     rep(i,0,q){
          int x; cin >> x; x--;
          cout << (dist[2][x] >= inf? -1: dist[2][x]) << '\n';
     }
     return 0-0;
}

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