Submission #874505

#	Time	Username	Problem	Language	Result	Execution time	Memory
874505		Alish	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	843 ms	7300 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);


ll mod = 1e9+7 ;

const int N = 3e4+23;
const ll INF= 1e18+23;

vector<int> g[N];
int d[N];
int b[N];
int n , m;
ll dist[N];
int vis[N];

void bfs(){
    fast_io
    for (int i=0; i<=n; i++) dist[i]=INF;
    dist[b[0]]=0;
    priority_queue<pll, vector<pll>, greater<pll> > q;
    q.push({0, b[0]});
    while(!q.empty()){
        int v=q.top().S; q.pop();
        if(vis[v]) continue;
        vis[v]=1;
        for (int d: g[v]){
            for (int i=1; v+i*d<n; i++){
                int u=i*d+v;
                    if(dist[u]>dist[v]+i){
                        dist[u]=dist[v]+i;
                        q.push({dist[u], u});
                    }

            }
            for (int i=1; v-i*d>=0; i++){
                int u=-i*d+v;
                if(dist[u]>dist[v]+i){
                    dist[u]=dist[v]+i;
                    q.push({dist[u], u});
                }

            }
        }

    }
}

int main()
{

    cin>>n>>m;
    for (int i=0; i<m; i++) cin>>b[i]>>d[i];
    for (int i=0; i<m; i++) g[b[i]].pb(d[i]);

    bfs();
    if(dist[b[1]]>=INF) dist[b[1]]=-1;
    cout<<dist[b[1]]<<endl;
}

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