# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
111896 | 2019-05-16T17:14:39 Z | mayhoubsaleh | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 1000 ms | 66268 KB |
#include <bits/stdc++.h> #define ll long long #define pb push_back #define inf 1e18+100 using namespace std; const ll N=30300; priority_queue<pair<ll,ll>>q; ll n,m; ll b[N],p[N],dist[N]; vector<ll>a[N]; vector<pair<ll,ll>>v[N]; void fil(ll id){ for(ll i=0;i<n;i++){ if(i==id||a[i].empty())continue; for(auto j:a[id]){ if((i%p[j])==(id%p[j])){ v[id].pb({i,abs(i-id)/p[j]}); } } } } int main(){ //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); scanf("%lld%lld",&n,&m); for(ll i=0;i<m;i++){ //cin>>b[i]>>p[i]; scanf("%lld%lld",&b[i],&p[i]); a[b[i]].pb(i); } for(ll i=0;i<n;i++){ if(!a[i].empty())fil(i); } /*for(ll i=0;i<n;i++){ if(v[i].empty())continue; cout<<i<<": "; for(auto j:v[i])cout<<'('<<j.first<<' '<<j.second<<')'<<" ";cout<<endl; }*/ for(ll i=0;i<n;i++){ dist[i]=inf; } q.push({0,b[0]}); dist[b[0]]=0; while(!q.empty()){ ll u=q.top().second,d=-q.top().first; q.pop(); if(d>dist[u])continue; for(auto i:v[u]){ ll ch=i.first,chd=i.second; if(chd+d<dist[ch]){ dist[ch]=chd+d; q.push({-dist[ch],ch}); } } } if(dist[b[1]]==inf){cout<<-1<<endl;return 0;} cout<<dist[b[1]]<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1792 KB | Output is correct |
2 | Correct | 3 ms | 1792 KB | Output is correct |
3 | Correct | 3 ms | 1792 KB | Output is correct |
4 | Correct | 3 ms | 1792 KB | Output is correct |
5 | Correct | 4 ms | 1792 KB | Output is correct |
6 | Correct | 4 ms | 1792 KB | Output is correct |
7 | Correct | 3 ms | 1792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1792 KB | Output is correct |
2 | Correct | 4 ms | 1792 KB | Output is correct |
3 | Correct | 3 ms | 1792 KB | Output is correct |
4 | Correct | 3 ms | 1792 KB | Output is correct |
5 | Correct | 3 ms | 1792 KB | Output is correct |
6 | Correct | 3 ms | 1792 KB | Output is correct |
7 | Correct | 4 ms | 1792 KB | Output is correct |
8 | Correct | 3 ms | 1792 KB | Output is correct |
9 | Correct | 3 ms | 1792 KB | Output is correct |
10 | Correct | 5 ms | 1792 KB | Output is correct |
11 | Correct | 8 ms | 2048 KB | Output is correct |
12 | Correct | 6 ms | 2176 KB | Output is correct |
13 | Correct | 18 ms | 6264 KB | Output is correct |
14 | Correct | 7 ms | 1920 KB | Output is correct |
15 | Correct | 8 ms | 1968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1792 KB | Output is correct |
2 | Correct | 3 ms | 1792 KB | Output is correct |
3 | Correct | 3 ms | 1792 KB | Output is correct |
4 | Correct | 3 ms | 1792 KB | Output is correct |
5 | Correct | 4 ms | 1792 KB | Output is correct |
6 | Correct | 3 ms | 1792 KB | Output is correct |
7 | Correct | 3 ms | 1792 KB | Output is correct |
8 | Correct | 4 ms | 1792 KB | Output is correct |
9 | Correct | 3 ms | 1792 KB | Output is correct |
10 | Correct | 5 ms | 1792 KB | Output is correct |
11 | Correct | 7 ms | 2048 KB | Output is correct |
12 | Correct | 6 ms | 2176 KB | Output is correct |
13 | Correct | 20 ms | 6424 KB | Output is correct |
14 | Correct | 7 ms | 1792 KB | Output is correct |
15 | Correct | 9 ms | 1792 KB | Output is correct |
16 | Correct | 8 ms | 1920 KB | Output is correct |
17 | Correct | 35 ms | 2276 KB | Output is correct |
18 | Correct | 28 ms | 1792 KB | Output is correct |
19 | Correct | 14 ms | 1792 KB | Output is correct |
20 | Correct | 215 ms | 66268 KB | Output is correct |
21 | Correct | 12 ms | 1792 KB | Output is correct |
22 | Correct | 16 ms | 1920 KB | Output is correct |
23 | Correct | 24 ms | 1920 KB | Output is correct |
24 | Correct | 72 ms | 2040 KB | Output is correct |
25 | Correct | 75 ms | 1920 KB | Output is correct |
26 | Correct | 15 ms | 6128 KB | Output is correct |
27 | Correct | 9 ms | 3956 KB | Output is correct |
28 | Correct | 90 ms | 2280 KB | Output is correct |
29 | Correct | 4 ms | 1792 KB | Output is correct |
30 | Correct | 5 ms | 1792 KB | Output is correct |
31 | Correct | 4 ms | 1792 KB | Output is correct |
32 | Correct | 3 ms | 1792 KB | Output is correct |
33 | Correct | 7 ms | 1920 KB | Output is correct |
34 | Correct | 6 ms | 1792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1792 KB | Output is correct |
2 | Correct | 2 ms | 1792 KB | Output is correct |
3 | Correct | 3 ms | 1792 KB | Output is correct |
4 | Correct | 2 ms | 1792 KB | Output is correct |
5 | Correct | 4 ms | 1792 KB | Output is correct |
6 | Correct | 3 ms | 1792 KB | Output is correct |
7 | Correct | 3 ms | 1792 KB | Output is correct |
8 | Correct | 3 ms | 1792 KB | Output is correct |
9 | Correct | 3 ms | 1764 KB | Output is correct |
10 | Correct | 4 ms | 1792 KB | Output is correct |
11 | Correct | 9 ms | 2048 KB | Output is correct |
12 | Correct | 5 ms | 2176 KB | Output is correct |
13 | Correct | 21 ms | 6328 KB | Output is correct |
14 | Correct | 8 ms | 1920 KB | Output is correct |
15 | Correct | 8 ms | 1920 KB | Output is correct |
16 | Correct | 7 ms | 1920 KB | Output is correct |
17 | Correct | 31 ms | 2304 KB | Output is correct |
18 | Correct | 28 ms | 1912 KB | Output is correct |
19 | Correct | 12 ms | 1792 KB | Output is correct |
20 | Correct | 219 ms | 66148 KB | Output is correct |
21 | Correct | 12 ms | 1792 KB | Output is correct |
22 | Correct | 15 ms | 1792 KB | Output is correct |
23 | Correct | 25 ms | 1920 KB | Output is correct |
24 | Correct | 84 ms | 2012 KB | Output is correct |
25 | Correct | 65 ms | 1920 KB | Output is correct |
26 | Correct | 13 ms | 6128 KB | Output is correct |
27 | Correct | 11 ms | 4084 KB | Output is correct |
28 | Correct | 108 ms | 2252 KB | Output is correct |
29 | Correct | 4 ms | 1792 KB | Output is correct |
30 | Correct | 4 ms | 1792 KB | Output is correct |
31 | Correct | 4 ms | 1792 KB | Output is correct |
32 | Correct | 5 ms | 1792 KB | Output is correct |
33 | Correct | 6 ms | 1920 KB | Output is correct |
34 | Correct | 6 ms | 1920 KB | Output is correct |
35 | Correct | 842 ms | 5544 KB | Output is correct |
36 | Correct | 129 ms | 2424 KB | Output is correct |
37 | Correct | 963 ms | 8672 KB | Output is correct |
38 | Execution timed out | 1047 ms | 6164 KB | Time limit exceeded |
39 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1792 KB | Output is correct |
2 | Correct | 4 ms | 1792 KB | Output is correct |
3 | Correct | 4 ms | 1792 KB | Output is correct |
4 | Correct | 4 ms | 1792 KB | Output is correct |
5 | Correct | 7 ms | 1792 KB | Output is correct |
6 | Correct | 3 ms | 1792 KB | Output is correct |
7 | Correct | 3 ms | 1792 KB | Output is correct |
8 | Correct | 1 ms | 1792 KB | Output is correct |
9 | Correct | 3 ms | 1792 KB | Output is correct |
10 | Correct | 6 ms | 1792 KB | Output is correct |
11 | Correct | 11 ms | 2048 KB | Output is correct |
12 | Correct | 6 ms | 2176 KB | Output is correct |
13 | Correct | 14 ms | 6264 KB | Output is correct |
14 | Correct | 5 ms | 1792 KB | Output is correct |
15 | Correct | 7 ms | 1920 KB | Output is correct |
16 | Correct | 7 ms | 1920 KB | Output is correct |
17 | Correct | 43 ms | 2296 KB | Output is correct |
18 | Correct | 25 ms | 1920 KB | Output is correct |
19 | Correct | 13 ms | 1792 KB | Output is correct |
20 | Correct | 213 ms | 66232 KB | Output is correct |
21 | Correct | 13 ms | 1792 KB | Output is correct |
22 | Correct | 15 ms | 1792 KB | Output is correct |
23 | Correct | 23 ms | 1916 KB | Output is correct |
24 | Correct | 65 ms | 2040 KB | Output is correct |
25 | Correct | 71 ms | 2040 KB | Output is correct |
26 | Correct | 14 ms | 6000 KB | Output is correct |
27 | Correct | 9 ms | 3956 KB | Output is correct |
28 | Correct | 105 ms | 2428 KB | Output is correct |
29 | Correct | 4 ms | 1792 KB | Output is correct |
30 | Correct | 3 ms | 1792 KB | Output is correct |
31 | Correct | 3 ms | 1792 KB | Output is correct |
32 | Correct | 5 ms | 1792 KB | Output is correct |
33 | Correct | 7 ms | 1920 KB | Output is correct |
34 | Correct | 7 ms | 1920 KB | Output is correct |
35 | Correct | 880 ms | 5500 KB | Output is correct |
36 | Correct | 134 ms | 2296 KB | Output is correct |
37 | Correct | 908 ms | 8600 KB | Output is correct |
38 | Execution timed out | 1084 ms | 6896 KB | Time limit exceeded |
39 | Halted | 0 ms | 0 KB | - |