제출 #139218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
139218		abacaba	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1076 ms	35248 KiB

skyscraper

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

const int inf = 2e9;
const int N = 3e4 + 1;
int n, m, d[N], x;
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);
    for(int i = 0; i < m; ++i) {
    	if(x > 1e7)
    		break;
    	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});
    		++x;
    	}
    	b = a[i].first;
    	cnt = 0;
    	while(b + p < n) {
    		b += p;
    		g[a[i].first].push_back({++cnt, b});
    		++x;
    	}
    }
    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;
}

컴파일 시 표준 에러 (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