제출 #202509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202509		arnold518	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	644 ms	72036 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()
{
    int i, j, k;
 
    scanf("%d%d", &N, &M);
    for(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(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(j=1; j<V[it].size(); j++)
            {
                int now=V[it][j], bef=V[it][j-1];
                for(k=bef+i; k<=now; k+=i) adj[bef].push_back({k, (k-bef)/i});
                for(k=now-i; k>=bef; k-=i) adj[now].push_back({k, (now-k)/i});
            }
            for(k=V[it].back()+i; k<N; k+=i) adj[V[it].back()].push_back({k, (k-V[it].back())/i});
            for(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(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]);
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=1; j<V[it].size(); j++)
                      ~^~~~~~~~~~~~~
skyscraper.cpp:26: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:30: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: 43 / 43