Submission #102410

#	Time	Username	Problem	Language	Result	Execution time	Memory
102410		Darksinian	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	496 ms	82720 KiB

skyscraper

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int N = 100002;
int vv[N];
set<pair<int,int> > vis;
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 pre=-1;
        int x = p[i].f,pr = p[i].s;
        if(vis.count({x,pr})) continue;
        for(int j = x%pr;j<n;j+=pr) {
            int w = abs((j-x)/pr);
            if(po[j].count(pr)) {
                if(pre == -1) {
                    pre = j;
                    continue;
                }
                w = abs((pre-j)/pr);
                g[pre].push_back({j,w});
                g[j].push_back({pre,w});
                pre = j;
                vis.insert({j,pr});
            }
            else g[x].push_back({j,w});
        }
        vis.insert({x,pr});
    }
    for(int i =0;i<n;i++) d[i] = 1e18;
    for(int i=0;i<n;i++) {
        for(auto u : g[i]) {
           // cout << i << " " << u.first << " " << u.second << endl;
        }
    }
    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] > w + u.second) {
                if(d[u.first] != 1e18) x.erase({d[u.first],u.first});
                d[u.first] = w + u.second;
                x.insert({d[u.first],u.first});
            }
        }
    }
    if(d[p[1].f] == 1e18) cout << -1;
    else cout << d[p[1].f];

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:46:18: warning: variable 'u' set but not used [-Wunused-but-set-variable]
         for(auto u : g[i]) {
                  ^

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