Submission #102403

#	Time	Username	Problem	Language	Result	Execution time	Memory
102403		Darksinian	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	10 ms	7424 KiB

skyscraper

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int N = 100002;
int vis[N],vv[N];
ll d[N];
pair<int,int> p[N];
vector<pair<int,int> > g[N];
map<int,int> po[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i =0;i<m;i++) {
        int a,b;
        cin >> a >> b;
        p[i] = {a,b};
        po[a][b] = i;
    }
    for(int i =0;i<m;i++) {
        int x = p[i].f,pr = p[i].s;
        for(int j = x%pr;j<n-(n-1-x)%pr;j+=pr) {
            int w = abs((j-x)/pr);
            if(!po[j].empty())g[x].push_back({j,w});
        }
    }
    for(int i =0;i<n;i++) d[i] = 1e18;
    set<pair<ll,ll> > x;
    x.insert({0,p[0].f});
    d[p[0].f] = 0;
    while(!x.empty()) {
        int v = x.begin()->second;
        ll w = x.begin()->first;
        x.erase({w,v});
        for(auto u : g[v]) {
            if(d[u.first] > d[v] + u.second) {
                if(d[u.first] != 1e18) x.erase({d[u.first],u.first});
                d[u.first] = d[v] + u.second;
                x.insert({d[u.first],u.first});
            }
        }
    }
    cout << d[p[1].f];

    return 0;
}

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