Submission #8383

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
8383	2014-09-13T16:07:16 Z	tncks0121	Your life (kriii2_Y)	C++	4 / 4	88 ms	7108 KB

Y

#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h> 
#include <time.h>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 100005;

int N, M;
vector<int> Gph[N_];
int table[N_];

int main() {
	scanf("%d%d", &N, &M);
	assert(1 <= N && N <= 100000);
	assert(0 <= M && M <= 200000);

	while(M--) {
		int x, y; scanf("%d%d", &x, &y);
		Gph[x].push_back(y);
		assert(1 <= x && x < y && y <= N);
	}

	for(int i = 2; i <= N; i++) table[i] = N+1;

	for(int u = 1; u <= N; u++) if(table[u] < N+1) {
		for(int i = 0; i < Gph[u].size(); i++) table[Gph[u][i]] = min(table[Gph[u][i]], table[u]+1);
	}

	if(table[N] > N) table[N] = -1;
	printf("%d\n", table[N]);



	return 0;
}

Subtask #1

1.0 / 1.0

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

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3940 KB	Output is correct
2	Correct	40 ms	6976 KB	Output is correct
3	Correct	52 ms	6976 KB	Output is correct
4	Correct	60 ms	6976 KB	Output is correct
5	Correct	56 ms	6976 KB	Output is correct
6	Correct	40 ms	6976 KB	Output is correct
7	Correct	36 ms	6976 KB	Output is correct
8	Correct	88 ms	7108 KB	Output is correct
9	Correct	44 ms	6976 KB	Output is correct
10	Correct	84 ms	6712 KB	Output is correct