제출 #1187224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187224		Warinchai	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	61 ms	118032 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,vector<int>>mp;
vector<pair<int,int>>adj[5000005];
bitset<5000005>vis;
int inf=1e15;
int have[30005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    int st=0,en=0;
    for(int i=0;i<m;i++){
        int b,p;cin>>b>>p;
        if(i==0)st=b;
        if(i==1)en=b;
        if(i!=1)mp[{b%p,p}].push_back(b);
        have[b]++;
    }
    int id=n-1;
    for(auto x:mp){
        int cur=x.first.first;
        int p=x.first.second;
        for(auto b:x.second)adj[b].push_back({id+(b-cur)/p+1,0});
        for(cur;cur<n;cur+=p){
            id++;
            if(have[cur])adj[id].push_back({cur,0});
            if(cur!=x.first.first)adj[id-1].push_back({id,1});
        }
        cur=x.first.first;
        for(auto b:x.second)adj[b].push_back({id+(b-cur)/p+1,0});
        for(cur;cur<n;cur+=p){
            id++;
            if(have[cur])adj[id].push_back({cur,0});
            if(cur!=x.first.first)adj[id].push_back({id-1,1});
        }
    }
    mp.clear();
    deque<pair<int,int>>dq;
    dq.push_back({0,st});
    int ans=0;
    while(!dq.empty()){
        auto [d,u]=dq.front();
        dq.pop_front();
        if(vis[u])continue;
        vis[u]=1;
        if(u==en){
            ans=d;
            break;
        }
        for(auto v:adj[u]){
            if(vis[v.first])continue;
            if(v.second)dq.push_back({d+1,v.first});
            else dq.push_front({d,v.first});
        }
    }
    if(ans==inf)cout<<-1;
    else cout<<ans;
}

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

skyscraper.cpp:6:9: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
    6 | int inf=1e15;
      |         ^~~~

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