제출 #317719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
317719		ali_tavakoli	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	412 ms	262148 KiB

skyscraper

//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
//typedef sh short int
#define endl '\n'
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast")

const int N = 3e4 + 5, M = 3e4 + 5, inf = 1e9 + 5;

int n, m, b[M], p[M], dis[M], mm = 2;
vector<int> adj[M];
vector<int> pos[N];
set<pair<int, int> > bp;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> b[i] >> p[i];
        if(i > 1)
            bp.insert({b[i], p[i]});
    }

    for(auto x : bp)
    {
        bool is = 1;
        if(is)
        {
            b[mm] = x.F;
            p[mm] = x.S;
            mm++;
        }
    }
    bp.clear();

    for(int i = 0; i < mm; i++)
        pos[b[i]].pb(i);

    for(int i = 0; i < mm; i++)
    {
        int ptr = b[i];
        while(ptr < n)
        {
            for(auto x : pos[ptr])
                adj[i].pb(x);
            ptr += p[i];
        }

        ptr = b[i] - p[i];
        while(ptr >= 0)
        {
            for(auto x : pos[ptr])
                adj[i].pb(x);
            ptr -= p[i];
        }
    }

    for(int i = 1; i < mm + 5; i++)
        dis[i] = inf;
    set<pair<int, int> > st;
    st.insert({0, 0});
    while(st.size())
    {
        auto x = *st.begin();
        //cout << x.S << endl;
        st.erase(x);
        for(auto v : adj[x.S])
        {
            int dist = abs(b[v] - b[x.S]) / p[x.S];
            if(x.F + dist < dis[v])
            {
                dis[v] = x.F + dist;
                st.insert({dis[v], v});
            }
        }
    }
    st.clear();
    if(dis[1] == inf)
        cout << -1 << endl;
    else
        cout << dis[1] << endl;
    //cout << dis[1] << endl;
}

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