Submission #9769

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9769	2014-09-28T08:51:42 Z	levant916	Your life (kriii2_Y)	C++	4 / 4	196 ms	5144 KB

Y

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int dp[100001];
int M, N;
typedef pair<int, int> PAIR;


bool cmp(PAIR x, PAIR y)  {
	if (x.first < y.first){
		return true;
	}
	else if (x.first == y.first) {
		return x.second < y.second;
	}
	else {
		return false;
	}
}
int main(void) {

	int x, y;
	vector<PAIR> edge;
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		edge.push_back(PAIR(x, y));
	}

	sort(edge.begin(), edge.end());

	
	for (vector<PAIR>::iterator itor = edge.begin(); itor != edge.end(); itor++) {
		x = itor->first; y = itor->second;
		if (x != 1 && dp[x] == 0) continue;
		if (dp[y] == 0 || dp[y] > dp[x] + 1) {
			dp[y] = dp[x] + 1;
		}
	}
	

	if (dp[N] == 0) cout << -1 << endl;
	else cout << dp[N] << endl;
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2068 KB	Output is correct
2	Correct	0 ms	2068 KB	Output is correct
3	Correct	0 ms	2068 KB	Output is correct
4	Correct	0 ms	2068 KB	Output is correct
5	Correct	0 ms	2068 KB	Output is correct
6	Correct	0 ms	2068 KB	Output is correct
7	Correct	0 ms	2068 KB	Output is correct
8	Correct	0 ms	2068 KB	Output is correct
9	Correct	0 ms	2068 KB	Output is correct
10	Correct	60 ms	3608 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2068 KB	Output is correct
2	Correct	104 ms	3608 KB	Output is correct
3	Correct	148 ms	5144 KB	Output is correct
4	Correct	124 ms	5144 KB	Output is correct
5	Correct	140 ms	5144 KB	Output is correct
6	Correct	100 ms	3608 KB	Output is correct
7	Correct	84 ms	3608 KB	Output is correct
8	Correct	196 ms	5144 KB	Output is correct
9	Correct	120 ms	3608 KB	Output is correct
10	Correct	192 ms	5144 KB	Output is correct