oj.uz

Submission #205588

# Submission time Handle Problem Language Result Execution time Memory
205588 2020-02-29T08:54:19 Z kshitij_sodani Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 235556 KB 
#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;
//typedef int64_t int;
//#define mp make_pairr
#define pb push_back
/*#define a first
#define b second*/
#define endl "\n"
 int dis[2001][2001];
 
 int b[2001];
	int p[2001];
struct pairr{
	int a;
	int b;

};
vector<pairr> adj[2001][2001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin>>n>>m;
	
	//map<pairr<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]){
			pairr ac;
			ac.a=j;
			ac.b=i;
			adj[j+p[i]][i].pb(ac);
			ac.b=m;
			adj[j+p[i]][i].pb(ac);
		}
		for(int j=b[i]+p[i];j<n;j=j+p[i]){
			pairr ac;
			ac.a=j;
			ac.b=i;
			adj[j-p[i]][i].pb(ac);
			ac.b=m;
			adj[j-p[i]][i].pb(ac);
		}
			pairr ac;
			ac.a=b[i];
			ac.b=i;
		adj[b[i]][m].pb(ac);
	}



	
	memset(dis,-1,sizeof(dis));
	dis[b[0]][m]=0;
	dis[b[0]][0]=0;
	deque<pairr> aaa;
	pairr ac;
			ac.a=b[0];
			ac.b=0;
	aaa.push_back(ac);
	ac.b=m;
	aaa.push_back(ac);
	while(!aaa.empty()){
		pairr 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 74 ms 110072 KB Output is correct
2 Correct 76 ms 110072 KB Output is correct
3 Correct 77 ms 110072 KB Output is correct
4 Correct 83 ms 110076 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 110072 KB Output is correct
2 Correct 74 ms 110076 KB Output is correct
3 Correct 75 ms 110072 KB Output is correct
4 Correct 76 ms 110072 KB Output is correct
5 Correct 77 ms 110072 KB Output is correct
6 Correct 76 ms 110072 KB Output is correct
7 Correct 77 ms 110072 KB Output is correct
8 Correct 76 ms 110072 KB Output is correct
9 Correct 76 ms 110072 KB Output is correct
10 Correct 77 ms 110072 KB Output is correct
11 Correct 82 ms 110328 KB Output is correct
12 Correct 106 ms 116216 KB Output is correct
13 Correct 109 ms 116216 KB Output is correct
14 Correct 79 ms 110200 KB Output is correct
15 Correct 79 ms 110200 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 110088 KB Output is correct
2 Correct 77 ms 110072 KB Output is correct
3 Correct 76 ms 110072 KB Output is correct
4 Correct 76 ms 110072 KB Output is correct
5 Correct 74 ms 110072 KB Output is correct
6 Correct 78 ms 110072 KB Output is correct
7 Correct 76 ms 110072 KB Output is correct
8 Correct 81 ms 110072 KB Output is correct
9 Correct 78 ms 110072 KB Output is correct
10 Correct 78 ms 110072 KB Output is correct
11 Correct 78 ms 110516 KB Output is correct
12 Correct 103 ms 116216 KB Output is correct
13 Correct 111 ms 116344 KB Output is correct
14 Correct 79 ms 110204 KB Output is correct
15 Correct 80 ms 110200 KB Output is correct
16 Correct 77 ms 110200 KB Output is correct
17 Correct 87 ms 110712 KB Output is correct
18 Correct 85 ms 110200 KB Output is correct
19 Correct 77 ms 110200 KB Output is correct
20 Execution timed out 1103 ms 235376 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 110072 KB Output is correct
2 Correct 75 ms 110200 KB Output is correct
3 Correct 77 ms 110072 KB Output is correct
4 Correct 76 ms 110072 KB Output is correct
5 Correct 77 ms 110020 KB Output is correct
6 Correct 77 ms 109988 KB Output is correct
7 Correct 77 ms 110016 KB Output is correct
8 Correct 80 ms 110180 KB Output is correct
9 Correct 76 ms 110072 KB Output is correct
10 Correct 76 ms 110072 KB Output is correct
11 Correct 79 ms 110332 KB Output is correct
12 Correct 107 ms 116216 KB Output is correct
13 Correct 110 ms 116348 KB Output is correct
14 Correct 77 ms 110200 KB Output is correct
15 Correct 76 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 82 ms 110200 KB Output is correct
19 Correct 78 ms 110200 KB Output is correct
20 Execution timed out 1107 ms 235468 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 110072 KB Output is correct
2 Correct 75 ms 110072 KB Output is correct
3 Correct 80 ms 110072 KB Output is correct
4 Correct 77 ms 110052 KB Output is correct
5 Correct 76 ms 110072 KB Output is correct
6 Correct 74 ms 110076 KB Output is correct
7 Correct 77 ms 110072 KB Output is correct
8 Correct 76 ms 110068 KB Output is correct
9 Correct 75 ms 110072 KB Output is correct
10 Correct 77 ms 110100 KB Output is correct
11 Correct 79 ms 110328 KB Output is correct
12 Correct 108 ms 116216 KB Output is correct
13 Correct 111 ms 116216 KB Output is correct
14 Correct 79 ms 110328 KB Output is correct
15 Correct 76 ms 110204 KB Output is correct
16 Correct 76 ms 110200 KB Output is correct
17 Correct 87 ms 110712 KB Output is correct
18 Correct 77 ms 110200 KB Output is correct
19 Correct 77 ms 110200 KB Output is correct
20 Execution timed out 1105 ms 235556 KB Time limit exceeded
21 Halted 0 ms 0 KB -