Submission #139215

#	Time	Username	Problem	Language	Result	Execution time	Memory
139215		abacaba	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	567 ms	262148 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

const int inf = 2e9;
const int N = 3e4 + 15;
int n, m, d[N];
vector <pair <int, int> > g[N];
pair <int, int> a[N];
unordered_set <int> mod_used[N];
set <pair <int, int> > q;

int main() {
	fill(d, d + N, inf);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i)
    	scanf("%d%d", &a[i].first, &a[i].second);
    for(int i = 0; i < m; ++i) {
    	int b = a[i].first, p = a[i].second;
    	if(mod_used[p].find(b) != mod_used[p].end())
    		continue;
    	mod_used[p].insert(b);
    	int cnt = 0;
    	while(b - p >= 0) {
    		b -= p;
    		g[a[i].first].push_back({++cnt, b});
    	}
    	b = a[i].first;
    	cnt = 0;
    	while(b + p < n) {
    		b += p;
    		g[a[i].first].push_back({++cnt, b});
    	}
    }
    d[a[0].first] = 0;
    q.insert({0, a[0].first});
    while(!q.empty()) {
    	int v = q.begin()->second;
    	q.erase(q.begin());
    	for(pair <int, int> to : g[v]) {
    		if(d[to.second] > d[v] + to.first) {
    			q.erase({d[to.second], to.second});
    			d[to.second] = d[v] + to.first;
    			q.insert({d[to.second], to.second});
    		}
    	}
    }
    if(d[a[1].first] == inf)
    	puts("-1");
    else
    	printf("%d\n", d[a[1].first]);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:16:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d", &a[i].first, &a[i].second);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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