oj.uz

Submission #21969

# Submission time Handle Problem Language Result Execution time Memory
21969 2017-04-27T21:38:52 Z Hiasat Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 166 ms 21944 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;

const int MOD = 1e9 + 7;

const ll oo = 1e15;

typedef long long ll;

int n , m;

pii d[2010];

bool vis[2010][2010];
int cost[2010][2010];

vector<int> dogs[2010];


int main() {
 	//freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for (int i = 0; i < m; ++i){
		scanf("%d%d",&d[i].first,&d[i].second);
		dogs[d[i].first].push_back(i);
	}
	deque<pii> q;
	cost[d[0].first][0] = 0;
	vis[d[0].first][0] = 1;
	q.push_front(make_pair(d[0].first,0));
	while(!q.empty()){
		pii src = q.front();
		if(src.first == d[1].first){
			printf("%d\n", cost[src.first][src.second]);
			return 0;
		}
		q.pop_front();
		for (int i = 0; i < dogs[src.first].size(); ++i){
			int nw = dogs[src.first][i];
			if(vis[src.first][nw])
				continue;
			vis[src.first][nw] = 1;
			cost[src.first][nw] = cost[src.first][src.second];
			q.push_front(make_pair(src.first,nw));
		}
		for(int i = -1 ; i <= 1 ; i+= 2){
			int nw = src.first + d[src.second].second * i;
			if(nw < 0 || nw >= n)
				continue;
			if(vis[nw][src.second])
				continue;
			vis[nw][src.second]=1;
			cost[nw][src.second] = 1 + cost[src.first][src.second];
			q.push_back(make_pair(nw,src.second));
		}
	}
	puts("-1");
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < dogs[src.first].size(); ++i){
                     ^
skyscraper.cpp:30:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
skyscraper.cpp:32:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&d[i].first,&d[i].second);
                                         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21812 KB Output is correct
2 Correct 0 ms 21812 KB Output is correct
3 Correct 0 ms 21812 KB Output is correct
4 Correct 0 ms 21812 KB Output is correct
5 Correct 0 ms 21812 KB Output is correct
6 Correct 0 ms 21812 KB Output is correct
7 Correct 0 ms 21812 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21812 KB Output is correct
2 Correct 0 ms 21812 KB Output is correct
3 Correct 0 ms 21812 KB Output is correct
4 Correct 0 ms 21812 KB Output is correct
5 Correct 0 ms 21812 KB Output is correct
6 Correct 0 ms 21812 KB Output is correct
7 Correct 0 ms 21812 KB Output is correct
8 Correct 0 ms 21812 KB Output is correct
9 Correct 0 ms 21812 KB Output is correct
10 Correct 0 ms 21812 KB Output is correct
11 Correct 0 ms 21812 KB Output is correct
12 Correct 0 ms 21812 KB Output is correct
13 Correct 6 ms 21812 KB Output is correct
14 Correct 3 ms 21812 KB Output is correct
15 Correct 0 ms 21812 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21812 KB Output is correct
2 Correct 0 ms 21812 KB Output is correct
3 Correct 0 ms 21812 KB Output is correct
4 Correct 0 ms 21812 KB Output is correct
5 Correct 0 ms 21812 KB Output is correct
6 Correct 0 ms 21812 KB Output is correct
7 Correct 0 ms 21812 KB Output is correct
8 Correct 0 ms 21812 KB Output is correct
9 Correct 0 ms 21812 KB Output is correct
10 Correct 0 ms 21812 KB Output is correct
11 Correct 0 ms 21812 KB Output is correct
12 Correct 0 ms 21812 KB Output is correct
13 Correct 6 ms 21812 KB Output is correct
14 Correct 0 ms 21812 KB Output is correct
15 Correct 0 ms 21812 KB Output is correct
16 Correct 0 ms 21812 KB Output is correct
17 Correct 6 ms 21812 KB Output is correct
18 Correct 0 ms 21812 KB Output is correct
19 Correct 0 ms 21812 KB Output is correct
20 Correct 166 ms 21944 KB Output is correct
21 Correct 0 ms 21812 KB Output is correct
22 Correct 0 ms 21812 KB Output is correct
23 Correct 3 ms 21812 KB Output is correct
24 Correct 0 ms 21812 KB Output is correct
25 Correct 0 ms 21812 KB Output is correct
26 Correct 3 ms 21812 KB Output is correct
27 Correct 0 ms 21812 KB Output is correct
28 Correct 0 ms 21944 KB Output is correct
29 Correct 9 ms 21812 KB Output is correct
30 Correct 0 ms 21812 KB Output is correct
31 Correct 3 ms 21812 KB Output is correct
32 Correct 0 ms 21812 KB Output is correct
33 Correct 9 ms 21812 KB Output is correct
34 Correct 6 ms 21812 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21812 KB Output is correct
2 Correct 0 ms 21812 KB Output is correct
3 Correct 0 ms 21812 KB Output is correct
4 Correct 0 ms 21812 KB Output is correct
5 Correct 0 ms 21812 KB Output is correct
6 Correct 0 ms 21812 KB Output is correct
7 Correct 0 ms 21812 KB Output is correct
8 Correct 0 ms 21812 KB Output is correct
9 Correct 0 ms 21812 KB Output is correct
10 Correct 0 ms 21812 KB Output is correct
11 Correct 0 ms 21812 KB Output is correct
12 Correct 0 ms 21812 KB Output is correct
13 Correct 6 ms 21812 KB Output is correct
14 Correct 0 ms 21812 KB Output is correct
15 Correct 0 ms 21812 KB Output is correct
16 Correct 0 ms 21812 KB Output is correct
17 Correct 0 ms 21812 KB Output is correct
18 Correct 0 ms 21812 KB Output is correct
19 Correct 0 ms 21812 KB Output is correct
20 Correct 96 ms 21944 KB Output is correct
21 Correct 0 ms 21812 KB Output is correct
22 Correct 0 ms 21812 KB Output is correct
23 Correct 0 ms 21812 KB Output is correct
24 Correct 3 ms 21812 KB Output is correct
25 Correct 0 ms 21812 KB Output is correct
26 Correct 3 ms 21812 KB Output is correct
27 Correct 3 ms 21812 KB Output is correct
28 Correct 3 ms 21944 KB Output is correct
29 Correct 0 ms 21812 KB Output is correct
30 Correct 0 ms 21812 KB Output is correct
31 Correct 3 ms 21812 KB Output is correct
32 Correct 3 ms 21812 KB Output is correct
33 Correct 9 ms 21812 KB Output is correct
34 Correct 6 ms 21812 KB Output is correct
35 Incorrect 0 ms 21812 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21812 KB Output is correct
2 Correct 0 ms 21812 KB Output is correct
3 Correct 0 ms 21812 KB Output is correct
4 Correct 0 ms 21812 KB Output is correct
5 Correct 0 ms 21812 KB Output is correct
6 Correct 0 ms 21812 KB Output is correct
7 Correct 0 ms 21812 KB Output is correct
8 Correct 0 ms 21812 KB Output is correct
9 Correct 0 ms 21812 KB Output is correct
10 Correct 0 ms 21812 KB Output is correct
11 Correct 0 ms 21812 KB Output is correct
12 Correct 0 ms 21812 KB Output is correct
13 Correct 6 ms 21812 KB Output is correct
14 Correct 0 ms 21812 KB Output is correct
15 Correct 0 ms 21812 KB Output is correct
16 Correct 0 ms 21812 KB Output is correct
17 Correct 3 ms 21812 KB Output is correct
18 Correct 0 ms 21812 KB Output is correct
19 Correct 0 ms 21812 KB Output is correct
20 Correct 113 ms 21944 KB Output is correct
21 Correct 0 ms 21812 KB Output is correct
22 Correct 0 ms 21812 KB Output is correct
23 Correct 3 ms 21812 KB Output is correct
24 Correct 3 ms 21812 KB Output is correct
25 Correct 3 ms 21812 KB Output is correct
26 Correct 0 ms 21812 KB Output is correct
27 Correct 0 ms 21812 KB Output is correct
28 Correct 6 ms 21944 KB Output is correct
29 Correct 0 ms 21812 KB Output is correct
30 Correct 6 ms 21812 KB Output is correct
31 Correct 3 ms 21812 KB Output is correct
32 Correct 0 ms 21812 KB Output is correct
33 Correct 13 ms 21812 KB Output is correct
34 Correct 3 ms 21812 KB Output is correct
35 Incorrect 0 ms 21812 KB Output isn't correct
36 Halted 0 ms 0 KB -