oj.uz

Submission #15711

# Submission time Handle Problem Language Result Execution time Memory
15711 2015-07-16T08:08:51 Z cki86201 Jakarta Skyscrapers (APIO15_skyscraper) C++
0 / 100
 0 ms 23028 KB 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<queue>
using namespace std;

#define X first
#define Y second
typedef pair<int, int> Pi;
const int MX = 30003;
const int SX = 170;

priority_queue <Pi, vector<Pi>, greater<Pi> > pq;
vector <Pi> E[MX];
int n, m;
int p[MX][2];
int chk[MX][SX+4];
int len[MX];

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++){
		scanf("%d%d", p[i], p[i] + 1);
		if (p[i][1] < SX)chk[p[i][0]][p[i][1]] = 1;
	}
	for (int i = 0; i < m; i++){
		for (int j = p[i][0] + p[i][1], l = 1; j < n; j += p[i][1], l++){
			E[p[i][0]].push_back(Pi(j, l));
			//if (p[i][1] < SX && chk[j][p[i][1]])break;
		}
	}
	for (int i = 0; i < m; i++){
		for (int j = p[i][0] - p[i][1], l = 1; j >= 0; j -= p[i][1], l++){
			E[p[i][0]].push_back(Pi(j, l));
			//if (p[i][1] < SX && chk[j][p[i][1]])break;
		}
	}
	pq.push(Pi(0, 0));
	for (int i = 1; i < n; i++)len[i] = 1e7;
	while (!pq.empty()){
		Pi t = pq.top();
		pq.pop();
		if (len[t.Y] != t.X)continue;
		if (t.Y == 1)break;
		for (int i = 0; i < (int)E[t.Y].size(); i++){
			Pi &w = E[t.Y][i];
			if (len[w.X] > len[t.Y] + w.Y){
				len[w.X] = len[t.Y] + w.Y;
				pq.push(Pi(len[w.X], w.X));
			}
		}
	}
	printf("%d", len[1] == 1e7 ? -1 : len[1]);
	return 0;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23028 KB Output is correct
2 Correct 0 ms 23028 KB Output is correct
3 Incorrect 0 ms 23028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23028 KB Output is correct
2 Correct 0 ms 23028 KB Output is correct
3 Incorrect 0 ms 23028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23028 KB Output is correct
2 Correct 0 ms 23028 KB Output is correct
3 Incorrect 0 ms 23028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23028 KB Output is correct
2 Correct 0 ms 23028 KB Output is correct
3 Incorrect 0 ms 23028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23028 KB Output is correct
2 Correct 0 ms 23028 KB Output is correct
3 Incorrect 0 ms 23028 KB Output isn't correct
4 Halted 0 ms 0 KB -