oj.uz

Submission #205587

# Submission time Handle Problem Language Result Execution time Memory
205587 2020-02-29T08:47:40 Z kshitij_sodani Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 235464 KB 
#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;
//typedef int64_t int;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
 int dis[2001][2001];
 vector<pair<int,int>> adj[2001][2001];
 int b[2001];
	int p[2001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin>>n>>m;
	
	//map<pair<int,int>,int> aa;
	
	for(int i=0;i<m;i++){
		cin>>b[i]>>p[i];
		for(int j=b[i]-p[i];j>=0;j=j-p[i]){
			adj[j+p[i]][i].pb(mp(j,i));
			adj[j+p[i]][i].pb(mp(j,m));
		}
		for(int j=b[i]+p[i];j<n;j=j+p[i]){
			adj[j-p[i]][i].pb(mp(j,i));
			adj[j-p[i]][i].pb(mp(j,m));
		}
		adj[b[i]][m].pb(mp(b[i],i));
	}



	
	memset(dis,-1,sizeof(dis));
	dis[b[0]][m]=0;
	dis[b[0]][0]=0;
	deque<pair<int,int>> aaa;
	aaa.push_back(mp(b[0],0));
	aaa.push_back(mp(b[0],m));
	while(!aaa.empty()){
		pair<int,int> x;


		 x=aaa.front();
		aaa.pop_front();
		int co=1;
		if(x.b==m){
			co=0;
		}
		for(auto nn:adj[x.a][x.b]){
			if(dis[nn.a][nn.b]==-1){
				dis[nn.a][nn.b]=dis[x.a][x.b]+co;
				if(co==0){
					aaa.push_front(nn);
				}
				else{
					aaa.push_back(nn);
				}
			}
		}
	}
	if(b[0]==b[1]){
		cout<<0<<endl;
		return 0;
	}

	cout<<dis[b[1]][m]<<endl;




	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 110072 KB Output is correct
2 Correct 76 ms 110072 KB Output is correct
3 Correct 75 ms 110072 KB Output is correct
4 Correct 76 ms 109944 KB Output is correct
5 Correct 76 ms 110076 KB Output is correct
6 Correct 75 ms 110072 KB Output is correct
7 Correct 73 ms 110072 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 110016 KB Output is correct
2 Correct 75 ms 109968 KB Output is correct
3 Correct 75 ms 110072 KB Output is correct
4 Correct 76 ms 110072 KB Output is correct
5 Correct 76 ms 110076 KB Output is correct
6 Correct 77 ms 110080 KB Output is correct
7 Correct 76 ms 110072 KB Output is correct
8 Correct 76 ms 110072 KB Output is correct
9 Correct 75 ms 110072 KB Output is correct
10 Correct 76 ms 110072 KB Output is correct
11 Correct 80 ms 110328 KB Output is correct
12 Correct 108 ms 116216 KB Output is correct
13 Correct 110 ms 116216 KB Output is correct
14 Correct 78 ms 110200 KB Output is correct
15 Correct 79 ms 110328 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 110080 KB Output is correct
2 Correct 78 ms 110072 KB Output is correct
3 Correct 76 ms 110072 KB Output is correct
4 Correct 75 ms 110072 KB Output is correct
5 Correct 75 ms 110072 KB Output is correct
6 Correct 80 ms 110072 KB Output is correct
7 Correct 77 ms 110084 KB Output is correct
8 Correct 75 ms 110076 KB Output is correct
9 Correct 74 ms 110072 KB Output is correct
10 Correct 78 ms 110072 KB Output is correct
11 Correct 78 ms 110332 KB Output is correct
12 Correct 110 ms 116220 KB Output is correct
13 Correct 110 ms 116216 KB Output is correct
14 Correct 76 ms 110268 KB Output is correct
15 Correct 82 ms 110200 KB Output is correct
16 Correct 77 ms 110200 KB Output is correct
17 Correct 88 ms 110712 KB Output is correct
18 Correct 78 ms 110328 KB Output is correct
19 Correct 79 ms 110204 KB Output is correct
20 Execution timed out 1064 ms 235368 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 110072 KB Output is correct
2 Correct 77 ms 110076 KB Output is correct
3 Correct 75 ms 110072 KB Output is correct
4 Correct 74 ms 110072 KB Output is correct
5 Correct 76 ms 110072 KB Output is correct
6 Correct 73 ms 110072 KB Output is correct
7 Correct 78 ms 110072 KB Output is correct
8 Correct 75 ms 110072 KB Output is correct
9 Correct 76 ms 110072 KB Output is correct
10 Correct 78 ms 110264 KB Output is correct
11 Correct 79 ms 110336 KB Output is correct
12 Correct 111 ms 116216 KB Output is correct
13 Correct 107 ms 116216 KB Output is correct
14 Correct 77 ms 110200 KB Output is correct
15 Correct 78 ms 110200 KB Output is correct
16 Correct 93 ms 110200 KB Output is correct
17 Correct 86 ms 110712 KB Output is correct
18 Correct 76 ms 110200 KB Output is correct
19 Correct 77 ms 110200 KB Output is correct
20 Execution timed out 1105 ms 235384 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 110072 KB Output is correct
2 Correct 76 ms 110072 KB Output is correct
3 Correct 76 ms 110072 KB Output is correct
4 Correct 78 ms 110072 KB Output is correct
5 Correct 76 ms 110072 KB Output is correct
6 Correct 77 ms 110072 KB Output is correct
7 Correct 76 ms 110072 KB Output is correct
8 Correct 79 ms 110072 KB Output is correct
9 Correct 75 ms 109996 KB Output is correct
10 Correct 76 ms 110072 KB Output is correct
11 Correct 80 ms 110328 KB Output is correct
12 Correct 107 ms 116216 KB Output is correct
13 Correct 111 ms 116216 KB Output is correct
14 Correct 81 ms 110200 KB Output is correct
15 Correct 79 ms 110204 KB Output is correct
16 Correct 78 ms 110200 KB Output is correct
17 Correct 86 ms 110712 KB Output is correct
18 Correct 79 ms 110328 KB Output is correct
19 Correct 83 ms 110200 KB Output is correct
20 Execution timed out 1110 ms 235464 KB Time limit exceeded
21 Halted 0 ms 0 KB -