Submission #734134

#	Time	Username	Problem	Language	Result	Execution time	Memory
734134		arnold518	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	543 ms	72020 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 3e4;
const int INF = 1e9;
 
int N, M, S, E;
vector<int> A[MAXN+10];
vector<pii> adj[MAXN+10];
int dist[MAXN+10];
 
struct Queue
{
    int u, w;
    bool operator < (const Queue &p) const { return w>p.w; }
};
 
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=1; i<=M; i++)
    {
        int b, p;
        scanf("%d%d", &b, &p);
        if(i==1) S=b;
        if(i==2) E=b;
        A[p].push_back(b);
    }
 
    for(int i=1; i<=MAXN; i++)
    {
        if(A[i].empty()) continue;
        vector<vector<int>> V;
        vector<int> comp;
        V.resize(i);
        for(auto it : A[i]) V[it%i].push_back(it);
        for(auto it : A[i]) comp.push_back(it%i);
 
        sort(comp.begin(), comp.end());
        comp.erase(unique(comp.begin(), comp.end()), comp.end());
 
        for(auto it : comp)
        {
            sort(V[it].begin(), V[it].end());
            for(int j=1; j<V[it].size(); j++)
            {
                int now=V[it][j], bef=V[it][j-1];
                for(int k=bef+i; k<=now; k+=i) adj[bef].push_back({k, (k-bef)/i});
                for(int k=now-i; k>=bef; k-=i) adj[now].push_back({k, (now-k)/i});
            }
            for(int k=V[it].back()+i; k<N; k+=i) adj[V[it].back()].push_back({k, (k-V[it].back())/i});
            for(int k=V[it][0]-i; k>=0; k-=i) adj[V[it][0]].push_back({k, (V[it][0]-k)/i});
        }
    }
 
    priority_queue<Queue> PQ;
    for(int i=0; i<N; i++) dist[i]=INF;
    PQ.push({S, 0}); dist[S]=0;
 
    while(!PQ.empty())
    {
        Queue now=PQ.top(); PQ.pop();
        if(dist[now.u]<now.w) continue;
        for(auto nxt : adj[now.u]) if(dist[nxt.first]>now.w+nxt.second) PQ.push({nxt.first, now.w+nxt.second}), dist[nxt.first]=now.w+nxt.second;
    }
    if(dist[E]==INF) dist[E]=-1;
    printf("%d\n", dist[E]);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int j=1; j<V[it].size(); j++)
      |                          ~^~~~~~~~~~~~~
skyscraper.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d%d", &b, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~

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