oj.uz

Submission #695152

# Submission time Handle Problem Language Result Execution time Memory
695152 2023-02-04T18:47:58 Z edogawa_something Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 793 ms 262144 KB 
#include<bits/stdc++.h>
#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef string st;
typedef bool bl;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
typedef vector<pii> vpi;
#define pu push
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fast ios_base::sync_with_stdio(0);cin.tie();
#define test ll qqqqq;cin>>qqqqq;while(qqqqq--)
#define F first
#define S second
#define forn(i,n) for(ll i=0;i<n;i++)
#define forx(i,j,n) for(ll i=j;i<n;i++)
#define pb push_back
#define pob pop_back
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define ub upper_bound
#define pof pop_front
#define pow powww
#define prtll(x) printf("%lld",x)
#define prtld(x) printf("%Lf",x)
#define prtst(x) printf("%s",x)
#define prtch(x) printf("%c",x)
#define measure chrono::high_resolution_clock::now()
const ll dx[]{1,0,-1,0};
const ll dy[]{0,-1,0,1};
const ll inf=2e18;
const ll mod=1e9+7;
const ll LM=2e7+1;
const ll M=2e6+1;
const ll MM=3002;
const ll MMM=501;
const ld pi=acos(-1);
//const ll mod=998244353;
ll pow(ll r,ll to,ll m=mod){
  ll res=1;
  r%=mod;
  while(to){
    if((to&1)){
      res*=r,res%=mod;
    }
    r*=r,r%=mod;
    to=(to>>1);
  }
  return res;
}
ll n,m,a[M],p[M],dis[MM][MM],ind0,ind1,dist[M];
vii v[M];
vpi vv[M];
void dij(ll ind){
  priority_queue<pii,vpi,greater<pii>>q;
  q.push({0,ind});
  dist[ind]=0;
  while(!q.empty()){
    pii x=q.top();
    q.pop();
    for(auto it:vv[x.S]){
      if(dist[it.F]>x.F+it.S)
      q.push({x.F+it.S,it.F}),dist[it.F]=x.F+it.S;
    }
  }
}
int main(){
  fast
  memset(dis,mod,sizeof dis);
  memset(dist,mod,sizeof dist);
  cin>>n>>m;
  forn(i,m){
    cin>>a[i]>>p[i];
    v[a[i]].pb(p[i]);
    if(i==0)
    ind0=a[i];
    if(i==1)
    ind1=a[i];
  }
  forn(i,n){
    forn(j,n){
      for(auto it:v[i]){
      if(abs(i-j)%it==0)
      dis[i][j]=min(dis[i][j],abs(i-j)/it);
      }
    }
  }
  forn(i,n){
    forn(j,n){
      if(dis[i][j]<mod)
      vv[i].pb({j,dis[i][j]});
    }
  }
  dij(ind0);
  if(dist[ind1]>=mod)
  dist[ind1]=-1;
  cout<<dist[ind1];
  return 0;
}
/*
 
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 180416 KB Output is correct
2 Correct 75 ms 180440 KB Output is correct
3 Correct 73 ms 180332 KB Output is correct
4 Correct 78 ms 180328 KB Output is correct
5 Correct 84 ms 180372 KB Output is correct
6 Correct 89 ms 180356 KB Output is correct
7 Correct 86 ms 180420 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 180360 KB Output is correct
2 Correct 99 ms 180448 KB Output is correct
3 Correct 85 ms 180332 KB Output is correct
4 Correct 74 ms 180412 KB Output is correct
5 Correct 81 ms 180328 KB Output is correct
6 Correct 80 ms 180412 KB Output is correct
7 Correct 80 ms 180408 KB Output is correct
8 Correct 75 ms 180336 KB Output is correct
9 Correct 76 ms 180460 KB Output is correct
10 Correct 74 ms 180464 KB Output is correct
11 Correct 77 ms 180632 KB Output is correct
12 Correct 80 ms 180488 KB Output is correct
13 Correct 78 ms 180608 KB Output is correct
14 Correct 78 ms 180484 KB Output is correct
15 Correct 75 ms 180508 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 180428 KB Output is correct
2 Correct 78 ms 180444 KB Output is correct
3 Correct 73 ms 180412 KB Output is correct
4 Correct 74 ms 180348 KB Output is correct
5 Correct 73 ms 180428 KB Output is correct
6 Correct 83 ms 180340 KB Output is correct
7 Correct 72 ms 180376 KB Output is correct
8 Correct 80 ms 180424 KB Output is correct
9 Correct 74 ms 180552 KB Output is correct
10 Correct 78 ms 180384 KB Output is correct
11 Correct 76 ms 180840 KB Output is correct
12 Correct 75 ms 180496 KB Output is correct
13 Correct 83 ms 180648 KB Output is correct
14 Correct 75 ms 180576 KB Output is correct
15 Correct 76 ms 180572 KB Output is correct
16 Correct 77 ms 180620 KB Output is correct
17 Correct 86 ms 181024 KB Output is correct
18 Correct 86 ms 180636 KB Output is correct
19 Correct 85 ms 180544 KB Output is correct
20 Correct 166 ms 244760 KB Output is correct
21 Correct 77 ms 180712 KB Output is correct
22 Correct 88 ms 180556 KB Output is correct
23 Correct 85 ms 180624 KB Output is correct
24 Correct 94 ms 180880 KB Output is correct
25 Correct 99 ms 180900 KB Output is correct
26 Correct 102 ms 180724 KB Output is correct
27 Correct 102 ms 180564 KB Output is correct
28 Correct 95 ms 181056 KB Output is correct
29 Correct 90 ms 181364 KB Output is correct
30 Correct 88 ms 180848 KB Output is correct
31 Correct 87 ms 181200 KB Output is correct
32 Correct 90 ms 181060 KB Output is correct
33 Correct 103 ms 181652 KB Output is correct
34 Correct 105 ms 181604 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 180392 KB Output is correct
2 Correct 77 ms 180552 KB Output is correct
3 Correct 73 ms 180368 KB Output is correct
4 Correct 82 ms 180420 KB Output is correct
5 Correct 74 ms 180428 KB Output is correct
6 Correct 85 ms 180436 KB Output is correct
7 Correct 73 ms 180428 KB Output is correct
8 Correct 84 ms 180432 KB Output is correct
9 Correct 71 ms 180400 KB Output is correct
10 Correct 75 ms 180412 KB Output is correct
11 Correct 72 ms 180512 KB Output is correct
12 Correct 74 ms 180504 KB Output is correct
13 Correct 74 ms 180640 KB Output is correct
14 Correct 73 ms 180536 KB Output is correct
15 Correct 75 ms 180452 KB Output is correct
16 Correct 75 ms 180560 KB Output is correct
17 Correct 83 ms 181008 KB Output is correct
18 Correct 94 ms 180628 KB Output is correct
19 Correct 85 ms 180592 KB Output is correct
20 Correct 168 ms 244748 KB Output is correct
21 Correct 83 ms 180424 KB Output is correct
22 Correct 86 ms 180612 KB Output is correct
23 Correct 95 ms 180580 KB Output is correct
24 Correct 108 ms 180776 KB Output is correct
25 Correct 102 ms 180740 KB Output is correct
26 Correct 121 ms 180740 KB Output is correct
27 Correct 113 ms 180656 KB Output is correct
28 Correct 108 ms 181056 KB Output is correct
29 Correct 100 ms 181272 KB Output is correct
30 Correct 89 ms 180940 KB Output is correct
31 Correct 103 ms 181256 KB Output is correct
32 Correct 100 ms 181000 KB Output is correct
33 Correct 115 ms 181660 KB Output is correct
34 Correct 121 ms 181568 KB Output is correct
35 Correct 274 ms 184036 KB Output is correct
36 Correct 115 ms 180992 KB Output is correct
37 Correct 297 ms 186928 KB Output is correct
38 Correct 398 ms 185968 KB Output is correct
39 Correct 399 ms 186356 KB Output is correct
40 Correct 373 ms 186104 KB Output is correct
41 Correct 381 ms 185932 KB Output is correct
42 Correct 454 ms 181432 KB Output is correct
43 Correct 435 ms 181420 KB Output is correct
44 Correct 508 ms 245432 KB Output is correct
45 Correct 376 ms 185672 KB Output is correct
46 Correct 389 ms 185548 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 180460 KB Output is correct
2 Correct 76 ms 180428 KB Output is correct
3 Correct 77 ms 180324 KB Output is correct
4 Correct 77 ms 180432 KB Output is correct
5 Correct 84 ms 180440 KB Output is correct
6 Correct 82 ms 180408 KB Output is correct
7 Correct 77 ms 180424 KB Output is correct
8 Correct 75 ms 180448 KB Output is correct
9 Correct 83 ms 180428 KB Output is correct
10 Correct 80 ms 180428 KB Output is correct
11 Correct 89 ms 180568 KB Output is correct
12 Correct 79 ms 180452 KB Output is correct
13 Correct 78 ms 180648 KB Output is correct
14 Correct 77 ms 180488 KB Output is correct
15 Correct 80 ms 180548 KB Output is correct
16 Correct 75 ms 180556 KB Output is correct
17 Correct 87 ms 180964 KB Output is correct
18 Correct 89 ms 180648 KB Output is correct
19 Correct 85 ms 180548 KB Output is correct
20 Correct 164 ms 244692 KB Output is correct
21 Correct 83 ms 180528 KB Output is correct
22 Correct 83 ms 180520 KB Output is correct
23 Correct 86 ms 180680 KB Output is correct
24 Correct 96 ms 180864 KB Output is correct
25 Correct 96 ms 180732 KB Output is correct
26 Correct 104 ms 180748 KB Output is correct
27 Correct 102 ms 180604 KB Output is correct
28 Correct 99 ms 180996 KB Output is correct
29 Correct 88 ms 181204 KB Output is correct
30 Correct 85 ms 180940 KB Output is correct
31 Correct 87 ms 181284 KB Output is correct
32 Correct 85 ms 180968 KB Output is correct
33 Correct 105 ms 181688 KB Output is correct
34 Correct 103 ms 181596 KB Output is correct
35 Correct 258 ms 184032 KB Output is correct
36 Correct 99 ms 180944 KB Output is correct
37 Correct 261 ms 186944 KB Output is correct
38 Correct 412 ms 186088 KB Output is correct
39 Correct 360 ms 186316 KB Output is correct
40 Correct 367 ms 186100 KB Output is correct
41 Correct 362 ms 185908 KB Output is correct
42 Correct 440 ms 181428 KB Output is correct
43 Correct 434 ms 181304 KB Output is correct
44 Correct 507 ms 245432 KB Output is correct
45 Correct 377 ms 185552 KB Output is correct
46 Correct 381 ms 185564 KB Output is correct
47 Runtime error 793 ms 262144 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -