Submission #48306

#	Time	Username	Problem	Language	Result	Execution time	Memory
48306		Unit	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1084 ms	63704 KiB

skyscraper

#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
 
#define se second
#define fi first
#define mk(a,b) make_pair(a,b)
 
typedef pair<int,int> pii;
typedef pair<int,pii> pipii;
 
int N,M;
vector<int> V[30010];
bool vis[30010];
int s,t;
unordered_set<int> st[30010];
 
int main()
{
    scanf("%d%d",&N,&M);
    for(int i = 0; i < M; i++)
    {
        int b,p;
        scanf("%d%d",&b,&p);
        V[b].push_back(p);
        if(i == 0)s = b;
        if(i == 1)t = b;
    }
  
    for(int i = 0; i < N; i++)
    {
        sort(V[i].begin(),V[i].end());
        V[i].erase(unique(V[i].begin(),V[i].end()),V[i].end());
    }
 
    queue<pipii> que;
    que.push(mk(1,mk(s,0)));
    while(que.size())
    {
        pipii now = que.front();
        que.pop();
        if(st[now.se.fi].count(now.se.se) != 0)continue;
        st[now.se.fi].insert(now.se.se);
        if(now.se.fi == t)
        {
            printf("%d\n",now.fi - 1);
            return 0;
        }
        if(!vis[now.se.fi])
        {
            vis[now.se.fi] = true;
            for(int i = 0; i < V[now.se.fi].size(); i++)
            {
                if(now.se.fi + V[now.se.fi][i] < N)
                    que.push(mk(now.fi + 1,mk(now.se.fi + V[now.se.fi][i],V[now.se.fi][i])));
                if(0 <= now.se.fi - V[now.se.fi][i])
                    que.push(mk(now.fi + 1,mk(now.se.fi - V[now.se.fi][i],V[now.se.fi][i])));
            }
        }
        vis[now.se.fi] = true;
        if(now.se.fi + now.se.se < N)que.push(mk(now.fi + 1,mk(now.se.fi + now.se.se,now.se.se)));
        if(0 <= now.se.fi - now.se.se)que.push(mk(now.fi + 1,mk(now.se.fi - now.se.se,now.se.se)));
    }
    printf("-1\n");
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:52:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < V[now.se.fi].size(); i++)
                            ~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&b,&p);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43