Submission #163456

#	Time	Username	Problem	Language	Result	Execution time	Memory
163456		Minnakhmetov	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	173 ms	6648 KiB

skyscraper

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

const int N = 3e4 + 5, INF = 1e9;
int d[N];
vector<int> v[N], q[N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    int finish, start;

    for (int i = 0; i < m; i++) {
    	int x, y;
    	cin >> x >> y;
    	v[x].push_back(y);

    	if (i == 0)
    		start = x;
    	if (i == 1)
    		finish = x;
    }

    fill(d, d + n, INF);

    q[0].push_back(start);
    d[start] = 0;

    for (int i = 0; i < N; i++) {
    	while (!q[i].empty()) {
	    	int node = q[i].back();
	    	q[i].pop_back();

	    	if (d[node] != i)
	    		continue;

	    	for (int x : v[node]) {
	    		int y = node + x, ct = 1;
	    		while (y < n) {
	    			if (d[y] > d[node] + ct) {
    					d[y] = d[node] + ct;
    					q[d[y]].push_back(y);
    				}
	    			ct++;
	    			y += x;
	    		}
	    		y = node - x, ct = 1;
	    		while (y >= 0) {
	    			if (d[y] > d[node] + ct) {
    					d[y] = d[node] + ct;
    					q[d[y]].push_back(y);
    				}
	    			ct++;
	    			y -= x;
	    		}
	    	}
    	}
    }

    cout << (d[finish] < INF ? d[finish] : -1);

    return 0;
} 

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:68:22: warning: 'finish' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout << (d[finish] < INF ? d[finish] : -1);
              ~~~~~~~~^

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