제출 #695065

#제출 시각아이디문제언어결과실행 시간메모리
695065edogawa_somethingJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
13 ms17912 KiB
#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[M]; void bfs(){ queue<ll>q; bl vis[M]; q.push(0); dis[0]=0; vis[0]=1; while(!q.empty()){ ll x=q.front(); q.pop(); forn(i,m){ if(a[i]%p[x]==a[x]%p[x]){ dis[i]=min(dis[i],abs(a[x]-a[i])/p[x]+dis[x]); if(!vis[i]) q.push(i),vis[i]=1; } } } } int main(){ fast memset(dis,mod,sizeof dis); cin>>n>>m; forn(i,m){ cin>>a[i]>>p[i]; } bfs(); if(dis[1]==mod) dis[1]=-1; cout<<dis[1]<<'\n'; return 0; } /* */
#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...