Submission #102405

#	Time	Username	Problem	Language	Result	Execution time	Memory
102405		Darksinian	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	604 ms	263168 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) {
            if(j == x) continue;
            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;
    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:32: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: 0 / 21
• Subtask 5: 0 / 43