# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
838123 | 2023-08-26T09:05:45 Z | 8pete8 | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 98 ms | 262144 KB |
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<limits.h> #include<cmath> #include<set> #include<algorithm> #include<bitset> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define pb push_back #define all(x) x.begin(),x.end() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define p push #define fastio ios::sync_with_stdio(false);cin.tie(NULL); using namespace std; const int mxn=3*1e4,mod=998244353,lg=42,root=173; void setIO(string name) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } int dist[(2*mxn*root)+10]; vector<pii>adj[(2*mxn*root)+10]; bitset<(2*mxn+10*root)+10>vis; int n,m; //make dummy node // n orginal + n node for each root(n) //node more than root id = mxn*ith+starting point void init(){ for(int i=1;i<root;i++){ for(int j=0;j<n;j++)adj[(mxn*i)+j].pb({j,0});//going down } for(int i=1;i<root;i++){ for(int j=i;j<n;j+=i){ //buid=ld edge for each i adj[(mxn*i)+j].pb({(mxn*i)+j-i,1}); adj[(mxn*i)+j-i].pb({(mxn*i)+j,1}); } } } int32_t main(){ fastio cin>>n>>m; int cnt=0; init(); for(int i=0;i<=mxn*root*2;i++)dist[i]=1e8; for(int i=0;i<m;i++){ int st,p;cin>>st>>p; if(p<=root)adj[st].pb({(p*mxn)+st,0}); else{ for(int j=st;j+p<n;j+=p){ adj[j].pb({j+p,1}); adj[j+p].pb({j,1}); } for(int j=st;j-p>=0;j-=p){ adj[j].pb({j-p,1}); adj[j-p].pb({j,1}); } //connect normal edge } //input } //dijkstra priority_queue<pii,vector<pii>,greater<pii>>pq; pq.push({0,0}); dist[0]=0; while(!pq.empty()){ int cur=pq.top().s; pq.pop(); if(vis[cur])continue; for(auto i:adj[cur]){ if(dist[i.f]>dist[cur]+i.s){ dist[i.f]=dist[cur]+i.s; pq.push({dist[i.f],i.f}); } } } cout<<((dist[1]==1e8)?-1:dist[1]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 87 ms | 262144 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 97 ms | 262144 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 88 ms | 262144 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 98 ms | 262144 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 86 ms | 262144 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |