Submission #112940

# Submission time Handle Problem Language Result Execution time Memory
112940 2019-05-22T17:35:46 Z nafis_shifat Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
1000 ms 14840 KB
#include<bits/stdc++.h>
#define mx 30009
#define pii pair<int,int>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int b[m+1],p[m+1];
    int sp[n+1]={};
    vector<pii> edg[mx];
    map<pair<int,int>,int> mp;
    for(int i=0;i<m;i++)
    {
        cin>>b[i];
        cin>>p[i];
        sp[b[i]]=p[i];
        
        
        
        
    }
    
    for(int i=0;i<m;i++)
    {
        int k=0;
        for(int j=b[i]+p[i];j<n;j+=p[i])
        {
            k++;
            if(sp[j]!=0 )
               edg[b[i]].push_back({j,k});
            if(mp[{j,p[i]}])break;
        }
        k=0;
        for(int j=b[i]-p[i];j>=0;j-=p[i])
        {
            k++;
            if(sp[j]!=0)
               edg[b[i]].push_back({j,k});
            if(mp[{j,p[i]}])break;
        }
        
        mp[{b[i],p[i]}]=1;
    }
    
   
    
    
   
    int dist[mx+1];
    for(int i=0;i<=mx;i++)dist[i]=(int)2e9;
    priority_queue<pii,vector<pii>,greater<pii>> pq;

    
    pq.push({0,b[0]});
    dist[b[0]]=0;
    int vis[mx+1]={};
    
    while(!pq.empty())
    {
        int u=pq.top().second;
       
        pq.pop();
        if(u==b[1])
        {
            cout<<dist[u]<<endl;
            return 0;
        }
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<edg[u].size();i++)
        {
            
            if(dist[edg[u][i].first]>dist[u]+edg[u][i].second)
            {
                dist[edg[u][i].first]=dist[u]+edg[u][i].second;
               
                pq.push({dist[edg[u][i].first],edg[u][i].first});
            }
        }
    }
    
    cout<<-1<<endl;
    
    
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<edg[u].size();i++)
                     ~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 2 ms 1280 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 2 ms 1280 KB Output is correct
6 Correct 2 ms 1280 KB Output is correct
7 Correct 2 ms 1280 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 3 ms 1280 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 2 ms 1280 KB Output is correct
6 Correct 2 ms 1280 KB Output is correct
7 Correct 2 ms 1280 KB Output is correct
8 Correct 3 ms 1280 KB Output is correct
9 Correct 3 ms 1280 KB Output is correct
10 Correct 3 ms 1408 KB Output is correct
11 Correct 5 ms 1664 KB Output is correct
12 Correct 6 ms 1536 KB Output is correct
13 Correct 4 ms 1408 KB Output is correct
14 Correct 5 ms 1664 KB Output is correct
15 Correct 5 ms 1664 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 2 ms 1280 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 3 ms 1280 KB Output is correct
8 Correct 2 ms 1280 KB Output is correct
9 Correct 3 ms 1280 KB Output is correct
10 Correct 3 ms 1408 KB Output is correct
11 Correct 4 ms 1536 KB Output is correct
12 Correct 5 ms 1536 KB Output is correct
13 Correct 4 ms 1408 KB Output is correct
14 Correct 8 ms 1664 KB Output is correct
15 Correct 5 ms 1664 KB Output is correct
16 Correct 5 ms 1536 KB Output is correct
17 Correct 9 ms 2432 KB Output is correct
18 Correct 5 ms 1664 KB Output is correct
19 Correct 4 ms 1536 KB Output is correct
20 Correct 7 ms 1732 KB Output is correct
21 Correct 4 ms 1408 KB Output is correct
22 Correct 4 ms 1664 KB Output is correct
23 Correct 5 ms 1792 KB Output is correct
24 Correct 8 ms 2176 KB Output is correct
25 Correct 6 ms 1792 KB Output is correct
26 Correct 352 ms 3860 KB Output is correct
27 Correct 245 ms 2672 KB Output is correct
28 Correct 11 ms 2944 KB Output is correct
29 Correct 44 ms 5112 KB Output is correct
30 Correct 8 ms 2432 KB Output is correct
31 Correct 15 ms 3328 KB Output is correct
32 Correct 12 ms 2816 KB Output is correct
33 Correct 80 ms 8824 KB Output is correct
34 Correct 85 ms 8748 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 3 ms 1280 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 2 ms 1280 KB Output is correct
8 Correct 3 ms 1280 KB Output is correct
9 Correct 2 ms 1280 KB Output is correct
10 Correct 3 ms 1408 KB Output is correct
11 Correct 6 ms 1664 KB Output is correct
12 Correct 7 ms 1536 KB Output is correct
13 Correct 4 ms 1408 KB Output is correct
14 Correct 5 ms 1664 KB Output is correct
15 Correct 5 ms 1664 KB Output is correct
16 Correct 5 ms 1536 KB Output is correct
17 Correct 9 ms 2432 KB Output is correct
18 Correct 5 ms 1792 KB Output is correct
19 Correct 4 ms 1664 KB Output is correct
20 Correct 7 ms 1792 KB Output is correct
21 Correct 3 ms 1408 KB Output is correct
22 Correct 5 ms 1664 KB Output is correct
23 Correct 5 ms 1792 KB Output is correct
24 Correct 8 ms 2176 KB Output is correct
25 Correct 6 ms 1792 KB Output is correct
26 Correct 304 ms 3668 KB Output is correct
27 Correct 232 ms 2672 KB Output is correct
28 Correct 11 ms 2940 KB Output is correct
29 Correct 30 ms 5112 KB Output is correct
30 Correct 8 ms 2304 KB Output is correct
31 Correct 16 ms 3328 KB Output is correct
32 Correct 10 ms 2788 KB Output is correct
33 Correct 75 ms 8820 KB Output is correct
34 Correct 58 ms 8824 KB Output is correct
35 Correct 73 ms 9348 KB Output is correct
36 Correct 11 ms 2688 KB Output is correct
37 Correct 159 ms 14840 KB Output is correct
38 Correct 145 ms 13944 KB Output is correct
39 Correct 132 ms 13916 KB Output is correct
40 Correct 147 ms 14004 KB Output is correct
41 Correct 132 ms 13912 KB Output is correct
42 Execution timed out 1078 ms 6364 KB Time limit exceeded
43 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 2 ms 1280 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 2 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 3 ms 1280 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 3 ms 1280 KB Output is correct
10 Correct 4 ms 1408 KB Output is correct
11 Correct 5 ms 1664 KB Output is correct
12 Correct 6 ms 1536 KB Output is correct
13 Correct 4 ms 1408 KB Output is correct
14 Correct 5 ms 1664 KB Output is correct
15 Correct 5 ms 1664 KB Output is correct
16 Correct 4 ms 1536 KB Output is correct
17 Correct 9 ms 2432 KB Output is correct
18 Correct 5 ms 1792 KB Output is correct
19 Correct 4 ms 1536 KB Output is correct
20 Correct 7 ms 1792 KB Output is correct
21 Correct 4 ms 1408 KB Output is correct
22 Correct 4 ms 1664 KB Output is correct
23 Correct 5 ms 1792 KB Output is correct
24 Correct 8 ms 2148 KB Output is correct
25 Correct 7 ms 1792 KB Output is correct
26 Correct 293 ms 3792 KB Output is correct
27 Correct 257 ms 2672 KB Output is correct
28 Correct 11 ms 2944 KB Output is correct
29 Correct 27 ms 5112 KB Output is correct
30 Correct 7 ms 2476 KB Output is correct
31 Correct 16 ms 3328 KB Output is correct
32 Correct 10 ms 2688 KB Output is correct
33 Correct 74 ms 8824 KB Output is correct
34 Correct 72 ms 8824 KB Output is correct
35 Correct 80 ms 9376 KB Output is correct
36 Correct 12 ms 2688 KB Output is correct
37 Correct 143 ms 14840 KB Output is correct
38 Correct 162 ms 13944 KB Output is correct
39 Correct 162 ms 13944 KB Output is correct
40 Correct 131 ms 13916 KB Output is correct
41 Correct 139 ms 13916 KB Output is correct
42 Execution timed out 1054 ms 6256 KB Time limit exceeded
43 Halted 0 ms 0 KB -