제출 #459350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
459350		azberjibiou	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	124 ms	190464 KiB

skyscraper

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=30010;
const int mxM=8000000;
const int mxK=100001;
const int MOD=1000000007;
const ll INF=9223372036854775807;
int N, M;
vector <int> v[mxN];
map <short, int> mp[mxN];
vector <pair<int, bool>> adj[mxM];
int idx;
int X, Y;
list <int> lst;
int dis[mxM];
bool Chk[mxM];
void zero_one_bfs()
{
    while(!lst.empty())
    {

        int now=lst.front();
        lst.pop_front();
        if(Chk[now])    continue;
        Chk[now]=true;
        for(pii nxt : adj[now])
        {
            if(dis[nxt.fir]>dis[now]+nxt.sec)
            {
                dis[nxt.fir]=dis[now]+nxt.sec;
                if(lst.empty() || dis[lst.front()]<=dis[nxt.fir])   lst.push_front(nxt.fir);
                else    lst.push_back(nxt.fir);
            }
        }
    }
}
int main()
{
    gibon
    cin >> N >> M;
    idx=N;
    for(int i=1;i<=M;i++)
    {
        int b, p;
        cin >> b >> p;
        if(i==1)    X=b;
        if(i==2)    Y=b;
        if(mp[b].end()==mp[b].find(p))
        {
            for(int j=b%p;j<N;j+=p)
            {
                mp[j][p]=idx;
                if(j>=p)
                {
                    adj[idx].push_back({idx-1, 1});
                    adj[idx-1].push_back({idx, 1});
                }
                idx++;
            }
        }
        v[b].push_back(p);
    }
    for(int i=0;i<N;i++)
    {
        for(auto iter=mp[i].begin();iter!=mp[i].end();iter++)
        {
            adj[iter->sec].push_back({i, 0});
        }
        for(int nxt : v[i])
        {
            adj[i].push_back({mp[i][nxt], 0});
        }
    }
    for(int i=0;i<idx;i++)
    {
        dis[i]=MOD;
    }
    dis[X]=0;
    lst.push_front(X);
    zero_one_bfs();
    if(dis[Y]==MOD) cout << -1;
    else    cout << dis[Y];
}

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