oj.uz

Submission #936545

# Submission time Handle Problem Language Result Execution time Memory
936545 2024-03-02T07:18:33 Z sleepntsheep Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 12 ms 43100 KB 
#include<string.h>
#include<stdio.h>
#include<utility>
#include<queue>
#define N 30000
#define S 170
#define N1 2*(S*N+N+N)
int lo(int a,int b){return a<b?a:b;}
int z=1e9,n,m,b[N],p[N],e[N1][3],ne,h[N1],d[N1];

void link(int u,int v,int w) {e[++ne][0]=v,e[ne][1]=w,e[ne][2]=h[u],h[u]=ne;}

int bp(int bb,int pp){return bb+30000*pp+30000;}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i){
        scanf("%d%d",b+i,p+i);
        if(p[i]<S){
            link(b[i],bp(b[i],p[i]),0);
        }else{
            for(int dd=1,j=b[i]-p[i];j>=0;j-=p[i],++dd)link(b[i],b[j],dd);
            for(int dd=1,j=b[i]+p[i];j<N;j+=p[i],++dd)link(b[i],b[j],dd);
        }
    }

    memset(d,63,sizeof d);
    std::priority_queue<std::pair<int,int>>pq;
    pq.emplace(-(d[b[0]]=0),b[0]);
    while(pq.size())
    {
        auto[c,u]=pq.top();c=-c;pq.pop();
        if(d[u]-c)continue;
        for(int j=h[u];j;j=e[j][2])if(d[e[j][0]]>c+e[j][1])
            pq.emplace(-(d[e[j][0]]=c+e[j][1]),e[j][0]);
        if(u>=30000){
            int bb,pp;
            bb=(u-30000)%30000;
            pp=(u-30000)/30000;
            if(bb==b[1])z=lo(z,c);
            //printf("AT %d %d\n",bb,pp);
            if(d[bb]>c)pq.emplace(-(d[bb]=c),bb);
            if(bb>=pp&&d[bp(bb-pp,pp)]>c+1)pq.emplace(-(d[bp(bb-pp,pp)]=c+1),bp(bb-pp,pp));
            if(bb+pp<n&&d[bp(bb+pp,pp)]>c+1)pq.emplace(-(d[bp(bb+pp,pp)]=c+1),bp(bb+pp,pp));
        } else
        {
            //printf("AT %d\n",u);
            if(u==b[1])z=lo(z,c);
        }

    }

    if(z<1e9)printf("%d",z);else puts("-1");
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d%d",b+i,p+i);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 42844 KB Output is correct
2 Correct 6 ms 42844 KB Output is correct
3 Correct 7 ms 42844 KB Output is correct
4 Correct 6 ms 42844 KB Output is correct
5 Correct 6 ms 42844 KB Output is correct
6 Correct 6 ms 42840 KB Output is correct
7 Correct 6 ms 42844 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42844 KB Output is correct
2 Correct 6 ms 42844 KB Output is correct
3 Correct 6 ms 42840 KB Output is correct
4 Correct 6 ms 42744 KB Output is correct
5 Correct 6 ms 42844 KB Output is correct
6 Correct 6 ms 42844 KB Output is correct
7 Correct 6 ms 42844 KB Output is correct
8 Correct 6 ms 42844 KB Output is correct
9 Correct 6 ms 42844 KB Output is correct
10 Correct 6 ms 42844 KB Output is correct
11 Correct 7 ms 42844 KB Output is correct
12 Correct 6 ms 42844 KB Output is correct
13 Correct 7 ms 42844 KB Output is correct
14 Correct 7 ms 42844 KB Output is correct
15 Correct 7 ms 42844 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42844 KB Output is correct
2 Correct 6 ms 42844 KB Output is correct
3 Correct 6 ms 42844 KB Output is correct
4 Correct 7 ms 42756 KB Output is correct
5 Correct 6 ms 42840 KB Output is correct
6 Correct 6 ms 42684 KB Output is correct
7 Correct 6 ms 42840 KB Output is correct
8 Correct 6 ms 42844 KB Output is correct
9 Correct 6 ms 42708 KB Output is correct
10 Correct 6 ms 42840 KB Output is correct
11 Correct 6 ms 42844 KB Output is correct
12 Correct 6 ms 42732 KB Output is correct
13 Correct 6 ms 42844 KB Output is correct
14 Correct 7 ms 42952 KB Output is correct
15 Correct 8 ms 42748 KB Output is correct
16 Incorrect 7 ms 43096 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42840 KB Output is correct
2 Correct 6 ms 42840 KB Output is correct
3 Correct 7 ms 42844 KB Output is correct
4 Correct 6 ms 42840 KB Output is correct
5 Correct 7 ms 42844 KB Output is correct
6 Correct 6 ms 42844 KB Output is correct
7 Correct 6 ms 42844 KB Output is correct
8 Correct 6 ms 42844 KB Output is correct
9 Correct 7 ms 42844 KB Output is correct
10 Correct 6 ms 42844 KB Output is correct
11 Correct 6 ms 42844 KB Output is correct
12 Correct 6 ms 42840 KB Output is correct
13 Correct 6 ms 42844 KB Output is correct
14 Correct 7 ms 42708 KB Output is correct
15 Correct 6 ms 42844 KB Output is correct
16 Incorrect 7 ms 43100 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42844 KB Output is correct
2 Correct 7 ms 42844 KB Output is correct
3 Correct 5 ms 42844 KB Output is correct
4 Correct 6 ms 42840 KB Output is correct
5 Correct 6 ms 42844 KB Output is correct
6 Correct 6 ms 42844 KB Output is correct
7 Correct 6 ms 42844 KB Output is correct
8 Correct 6 ms 42796 KB Output is correct
9 Correct 6 ms 42844 KB Output is correct
10 Correct 6 ms 42840 KB Output is correct
11 Correct 7 ms 42844 KB Output is correct
12 Correct 6 ms 42844 KB Output is correct
13 Correct 7 ms 42844 KB Output is correct
14 Correct 7 ms 42844 KB Output is correct
15 Correct 6 ms 42844 KB Output is correct
16 Incorrect 7 ms 43100 KB Output isn't correct
17 Halted 0 ms 0 KB -