# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
43926 | 2018-03-28T09:46:32 Z | Kerim | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 4 ms | 3228 KB |
#include "bits/stdc++.h" #define MAXN 100009 #define INF 1000000007 #define mp(x,y) make_pair(x,y) #define all(v) v.begin(),v.end() #define pb(x) push_back(x) #define wr cout<<"----------------"<<endl; #define ppb() pop_back() #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++) #define ff first #define ss second #define my_little_dodge 46 #define debug(x) cerr<< #x <<" = "<< x<<endl; using namespace std; typedef long long ll; typedef pair<int,int> PII; template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} int arr[MAXN],dis[MAXN]; vector<int>adj[MAXN]; int main(){ //~ freopen("file.in", "r", stdin); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); adj[u].pb(v);arr[i]=u; } priority_queue<pair<int,int> >q; q.push(mp(0,arr[1]));dis[0]=0; for(int i=1;i<n;i++) dis[i]=INF; while(!q.empty()){ int val=-q.top().ff; int nd=q.top().ss; q.pop(); if(dis[nd]!=val) continue; tr(it,adj[nd]){ int cost=*it; for(int i=1;;i++){ if(nd-cost*i<0 and nd+cost*i>=n) break; if(nd-cost*i>=0 and umin(dis[nd-cost*i],dis[nd]+i)) q.push(mp(-dis[nd-cost*i],nd-cost*i)); if(nd+cost*i<n and umin(dis[nd+cost*i],dis[nd]+i)) q.push(mp(-dis[nd+cost*i],nd+cost*i)); } } } if(dis[arr[2]]==INF) dis[arr[2]]=-1; printf("%d\n",dis[arr[2]]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2680 KB | Output is correct |
2 | Correct | 3 ms | 2680 KB | Output is correct |
3 | Correct | 3 ms | 2868 KB | Output is correct |
4 | Correct | 3 ms | 2868 KB | Output is correct |
5 | Correct | 4 ms | 2868 KB | Output is correct |
6 | Correct | 3 ms | 2932 KB | Output is correct |
7 | Correct | 3 ms | 2932 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2936 KB | Output is correct |
2 | Correct | 4 ms | 3060 KB | Output is correct |
3 | Correct | 3 ms | 3060 KB | Output is correct |
4 | Correct | 4 ms | 3060 KB | Output is correct |
5 | Correct | 3 ms | 3060 KB | Output is correct |
6 | Correct | 4 ms | 3060 KB | Output is correct |
7 | Correct | 3 ms | 3060 KB | Output is correct |
8 | Incorrect | 3 ms | 3128 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 3128 KB | Output is correct |
2 | Correct | 4 ms | 3128 KB | Output is correct |
3 | Correct | 4 ms | 3128 KB | Output is correct |
4 | Correct | 3 ms | 3128 KB | Output is correct |
5 | Correct | 4 ms | 3128 KB | Output is correct |
6 | Correct | 3 ms | 3128 KB | Output is correct |
7 | Correct | 4 ms | 3128 KB | Output is correct |
8 | Incorrect | 3 ms | 3128 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 3128 KB | Output is correct |
2 | Correct | 4 ms | 3128 KB | Output is correct |
3 | Correct | 3 ms | 3128 KB | Output is correct |
4 | Correct | 3 ms | 3128 KB | Output is correct |
5 | Correct | 4 ms | 3128 KB | Output is correct |
6 | Correct | 3 ms | 3128 KB | Output is correct |
7 | Correct | 4 ms | 3128 KB | Output is correct |
8 | Incorrect | 3 ms | 3128 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 3128 KB | Output is correct |
2 | Correct | 4 ms | 3128 KB | Output is correct |
3 | Correct | 3 ms | 3128 KB | Output is correct |
4 | Correct | 3 ms | 3128 KB | Output is correct |
5 | Correct | 3 ms | 3128 KB | Output is correct |
6 | Correct | 3 ms | 3228 KB | Output is correct |
7 | Correct | 4 ms | 3228 KB | Output is correct |
8 | Incorrect | 4 ms | 3228 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |