oj.uz

답안 #695100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
695100 2023-02-04T17:50:04 Z edogawa_something Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 103 ms 144208 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=1002;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 117680 KB Output is correct
2 Correct 59 ms 117712 KB Output is correct
3 Correct 60 ms 117764 KB Output is correct
4 Correct 58 ms 117764 KB Output is correct
5 Correct 59 ms 117708 KB Output is correct
6 Correct 59 ms 117648 KB Output is correct
7 Correct 73 ms 117776 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 117668 KB Output is correct
2 Correct 58 ms 117680 KB Output is correct
3 Correct 68 ms 117644 KB Output is correct
4 Correct 63 ms 117688 KB Output is correct
5 Correct 64 ms 117708 KB Output is correct
6 Correct 58 ms 117848 KB Output is correct
7 Correct 54 ms 117660 KB Output is correct
8 Correct 59 ms 117780 KB Output is correct
9 Correct 60 ms 117688 KB Output is correct
10 Correct 58 ms 117712 KB Output is correct
11 Correct 66 ms 117964 KB Output is correct
12 Correct 62 ms 117880 KB Output is correct
13 Correct 64 ms 118036 KB Output is correct
14 Correct 62 ms 117832 KB Output is correct
15 Correct 65 ms 117888 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 117708 KB Output is correct
2 Correct 66 ms 117764 KB Output is correct
3 Correct 55 ms 117836 KB Output is correct
4 Correct 56 ms 117764 KB Output is correct
5 Correct 61 ms 117688 KB Output is correct
6 Correct 64 ms 117772 KB Output is correct
7 Correct 59 ms 117772 KB Output is correct
8 Correct 58 ms 117776 KB Output is correct
9 Correct 68 ms 117732 KB Output is correct
10 Correct 59 ms 117708 KB Output is correct
11 Correct 61 ms 118044 KB Output is correct
12 Correct 59 ms 117768 KB Output is correct
13 Correct 60 ms 118016 KB Output is correct
14 Correct 58 ms 117884 KB Output is correct
15 Correct 60 ms 117896 KB Output is correct
16 Correct 62 ms 117896 KB Output is correct
17 Correct 67 ms 118464 KB Output is correct
18 Incorrect 99 ms 144176 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 117856 KB Output is correct
2 Correct 55 ms 117768 KB Output is correct
3 Correct 68 ms 117736 KB Output is correct
4 Correct 60 ms 117672 KB Output is correct
5 Correct 58 ms 117748 KB Output is correct
6 Correct 59 ms 117656 KB Output is correct
7 Correct 57 ms 117764 KB Output is correct
8 Correct 64 ms 117672 KB Output is correct
9 Correct 57 ms 117760 KB Output is correct
10 Correct 58 ms 117708 KB Output is correct
11 Correct 59 ms 117892 KB Output is correct
12 Correct 58 ms 117840 KB Output is correct
13 Correct 66 ms 117924 KB Output is correct
14 Correct 68 ms 117836 KB Output is correct
15 Correct 57 ms 117836 KB Output is correct
16 Correct 57 ms 117820 KB Output is correct
17 Correct 69 ms 118360 KB Output is correct
18 Incorrect 103 ms 144208 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 117772 KB Output is correct
2 Correct 60 ms 117772 KB Output is correct
3 Correct 57 ms 117740 KB Output is correct
4 Correct 58 ms 117644 KB Output is correct
5 Correct 57 ms 117716 KB Output is correct
6 Correct 57 ms 117704 KB Output is correct
7 Correct 58 ms 117768 KB Output is correct
8 Correct 58 ms 117728 KB Output is correct
9 Correct 59 ms 117660 KB Output is correct
10 Correct 58 ms 117832 KB Output is correct
11 Correct 59 ms 117968 KB Output is correct
12 Correct 59 ms 117836 KB Output is correct
13 Correct 59 ms 118044 KB Output is correct
14 Correct 65 ms 117856 KB Output is correct
15 Correct 60 ms 117780 KB Output is correct
16 Correct 59 ms 117868 KB Output is correct
17 Correct 65 ms 118268 KB Output is correct
18 Incorrect 93 ms 144140 KB Output isn't correct
19 Halted 0 ms 0 KB -