oj.uz

Submission #728049

# Submission time Handle Problem Language Result Execution time Memory
728049 2023-04-21T21:34:27 Z MohammadAghil Passport (JOI23_passport) C++17
100 / 100
 1172 ms 157888 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 54452 KB Output is correct
2 Correct 129 ms 54416 KB Output is correct
3 Correct 124 ms 54372 KB Output is correct
4 Correct 1154 ms 141032 KB Output is correct
5 Correct 558 ms 102560 KB Output is correct
6 Correct 378 ms 92980 KB Output is correct
7 Correct 570 ms 129576 KB Output is correct
8 Correct 319 ms 129904 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 54404 KB Output is correct
2 Correct 134 ms 54456 KB Output is correct
3 Correct 129 ms 54460 KB Output is correct
4 Correct 129 ms 54396 KB Output is correct
5 Correct 134 ms 54432 KB Output is correct
6 Correct 146 ms 54460 KB Output is correct
7 Correct 126 ms 54436 KB Output is correct
8 Correct 126 ms 54456 KB Output is correct
9 Correct 131 ms 54460 KB Output is correct
10 Correct 136 ms 54396 KB Output is correct
11 Correct 128 ms 54460 KB Output is correct
12 Correct 129 ms 54564 KB Output is correct
13 Correct 129 ms 54492 KB Output is correct
14 Correct 135 ms 54516 KB Output is correct
15 Correct 127 ms 54476 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 54404 KB Output is correct
2 Correct 134 ms 54456 KB Output is correct
3 Correct 129 ms 54460 KB Output is correct
4 Correct 129 ms 54396 KB Output is correct
5 Correct 134 ms 54432 KB Output is correct
6 Correct 146 ms 54460 KB Output is correct
7 Correct 126 ms 54436 KB Output is correct
8 Correct 126 ms 54456 KB Output is correct
9 Correct 131 ms 54460 KB Output is correct
10 Correct 136 ms 54396 KB Output is correct
11 Correct 128 ms 54460 KB Output is correct
12 Correct 129 ms 54564 KB Output is correct
13 Correct 129 ms 54492 KB Output is correct
14 Correct 135 ms 54516 KB Output is correct
15 Correct 127 ms 54476 KB Output is correct
16 Correct 133 ms 55180 KB Output is correct
17 Correct 133 ms 54980 KB Output is correct
18 Correct 158 ms 55432 KB Output is correct
19 Correct 135 ms 55356 KB Output is correct
20 Correct 131 ms 54888 KB Output is correct
21 Correct 130 ms 54972 KB Output is correct
22 Correct 144 ms 55360 KB Output is correct
23 Correct 149 ms 55220 KB Output is correct
24 Correct 130 ms 55060 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 54404 KB Output is correct
2 Correct 134 ms 54456 KB Output is correct
3 Correct 129 ms 54460 KB Output is correct
4 Correct 129 ms 54396 KB Output is correct
5 Correct 134 ms 54432 KB Output is correct
6 Correct 146 ms 54460 KB Output is correct
7 Correct 126 ms 54436 KB Output is correct
8 Correct 126 ms 54456 KB Output is correct
9 Correct 131 ms 54460 KB Output is correct
10 Correct 136 ms 54396 KB Output is correct
11 Correct 128 ms 54460 KB Output is correct
12 Correct 129 ms 54564 KB Output is correct
13 Correct 129 ms 54492 KB Output is correct
14 Correct 135 ms 54516 KB Output is correct
15 Correct 127 ms 54476 KB Output is correct
16 Correct 133 ms 55180 KB Output is correct
17 Correct 133 ms 54980 KB Output is correct
18 Correct 158 ms 55432 KB Output is correct
19 Correct 135 ms 55356 KB Output is correct
20 Correct 131 ms 54888 KB Output is correct
21 Correct 130 ms 54972 KB Output is correct
22 Correct 144 ms 55360 KB Output is correct
23 Correct 149 ms 55220 KB Output is correct
24 Correct 130 ms 55060 KB Output is correct
25 Correct 124 ms 54396 KB Output is correct
26 Correct 150 ms 54356 KB Output is correct
27 Correct 143 ms 55112 KB Output is correct
28 Correct 134 ms 54980 KB Output is correct
29 Correct 145 ms 54848 KB Output is correct
30 Correct 136 ms 55040 KB Output is correct
31 Correct 130 ms 55076 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 54452 KB Output is correct
2 Correct 129 ms 54416 KB Output is correct
3 Correct 124 ms 54372 KB Output is correct
4 Correct 1154 ms 141032 KB Output is correct
5 Correct 558 ms 102560 KB Output is correct
6 Correct 378 ms 92980 KB Output is correct
7 Correct 570 ms 129576 KB Output is correct
8 Correct 319 ms 129904 KB Output is correct
9 Correct 141 ms 54404 KB Output is correct
10 Correct 134 ms 54456 KB Output is correct
11 Correct 129 ms 54460 KB Output is correct
12 Correct 129 ms 54396 KB Output is correct
13 Correct 134 ms 54432 KB Output is correct
14 Correct 146 ms 54460 KB Output is correct
15 Correct 126 ms 54436 KB Output is correct
16 Correct 126 ms 54456 KB Output is correct
17 Correct 131 ms 54460 KB Output is correct
18 Correct 136 ms 54396 KB Output is correct
19 Correct 128 ms 54460 KB Output is correct
20 Correct 129 ms 54564 KB Output is correct
21 Correct 129 ms 54492 KB Output is correct
22 Correct 135 ms 54516 KB Output is correct
23 Correct 127 ms 54476 KB Output is correct
24 Correct 133 ms 55180 KB Output is correct
25 Correct 133 ms 54980 KB Output is correct
26 Correct 158 ms 55432 KB Output is correct
27 Correct 135 ms 55356 KB Output is correct
28 Correct 131 ms 54888 KB Output is correct
29 Correct 130 ms 54972 KB Output is correct
30 Correct 144 ms 55360 KB Output is correct
31 Correct 149 ms 55220 KB Output is correct
32 Correct 130 ms 55060 KB Output is correct
33 Correct 124 ms 54396 KB Output is correct
34 Correct 150 ms 54356 KB Output is correct
35 Correct 143 ms 55112 KB Output is correct
36 Correct 134 ms 54980 KB Output is correct
37 Correct 145 ms 54848 KB Output is correct
38 Correct 136 ms 55040 KB Output is correct
39 Correct 130 ms 55076 KB Output is correct
40 Correct 1172 ms 141432 KB Output is correct
41 Correct 601 ms 103180 KB Output is correct
42 Correct 695 ms 157888 KB Output is correct
43 Correct 723 ms 157872 KB Output is correct
44 Correct 392 ms 93116 KB Output is correct
45 Correct 448 ms 106032 KB Output is correct
46 Correct 428 ms 75704 KB Output is correct
47 Correct 796 ms 125992 KB Output is correct
48 Correct 536 ms 123524 KB Output is correct