Submission #139230

#	Time	Username	Problem	Language	Result	Execution time	Memory
139230		abacaba	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1071 ms	14072 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;
multiset <int> is[N];

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);
    	is[a[i].first].insert(a[i].second);
    }
    for(int i = 0; i < m; ++i) {
    	int b = a[i].first, p = a[i].second;
    	int cnt = 0;
    	is[b].erase(is[b].find(p));
    	if(is[b].find(p) != is[b].end())
    		continue;
    	while(b - p >= 0) {
    		b -= p;
    		g[a[i].first].push_back({++cnt, b});
    		if(is[b].find(p) != is[b].end())
    			break;
    	}
    	b = a[i].first;
    	cnt = 0;
    	while(b + p < n) {
    		b += p;
    		g[a[i].first].push_back({++cnt, b});
    		if(is[b].find(p) != is[b].end())
    			break;
    	}
    }
    d[a[0].first] = 0;
    q.push({0, a[0].first});
    while(!q.empty()) {
    	int v = q.top().second, dist = -q.top().first;
    	q.pop();
    	if(dist > d[v])
    		continue;
    	for(pair <int, int> to : g[v]) {
    		if(d[to.second] > d[v] + to.first) {
    			d[to.second] = d[v] + to.first;
    			q.push({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:15: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:17: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