Submission #139221

#	Time	Username	Problem	Language	Result	Execution time	Memory
139221		abacaba	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	1078 ms	2812 KiB

skyscraper

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

const int inf = 2e9;
const int N = 3e4 + 1;
int n, m, d[N];
vector <pair <int, int> > g[N];
pair <int, int> a[N];
unordered_set <int> mod_used[N];
priority_queue <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);
    d[a[0].first] = 0;
    q.push({0, 0});
    while(!q.empty()) {
    	int i = q.top().second, dist = -q.top().first;
    	int b = a[i].first, p = a[i].second;
    	int pos = b;
    	q.pop();
    	if(mod_used[p].find(b) != mod_used[p].end())
    		continue;
    	if(dist > d[b])
    		continue;
    	mod_used[p].insert(b);
    	int cnt = 0;
    	while(b - p >= 0) {
    		b -= p;
    		++cnt;
    		if(d[b] > d[pos] + cnt) {
    			d[b] = d[pos] + cnt;
    			q.push({-d[b], b});
    		}
    	}
    	b = a[i].first;
    	cnt = 0;
    	while(b + p < n) {
    		b += p;
    		++cnt;
    		if(d[b] > d[pos] + cnt) {
    			d[b] = d[pos] + cnt;
    			q.push({-d[b], b});
    		}
    	}
    }
    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: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43