oj.uz

Submission #374177

# Submission time Handle Problem Language Result Execution time Memory
374177 2021-03-06T20:11:58 Z Iwanttobreakfree Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 384 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int N,M,pos,S;
	cin>>N>>M;
	vector<pair<int,int> > doge(M);
	vector<int> distancia(N,1e9);
	for(int i=0;i<M;i++){
		cin>>pos>>S;
		doge[i]=make_pair(pos,S);
	}
	queue <pair<pair<int,int>,int> > q;
	q.push(make_pair(make_pair(doge[0].first,doge[0].second),0));
	distancia[0]=0;
	while(!q.empty()){
		int p=q.front().first.first;
		int mov=q.front().first.second;
		int jump=q.front().second;
		q.pop();
		int po=p;
		int mo=mov;
		int jum=jump;
	while(p){
			p-=mov;
			jump++;
			if(pos<0)break;
			if(distancia[p]>jump){
				distancia[p]=jump;
				//cout<<distancia[p]<<' '<<p<<' ';
				for(int i=0;i<M;i++)if(doge[i].first==p)q.push(make_pair(doge[i],jump));
			}
		}
	while(po<N){
		jum++;
		po+=mo;
		if(po>=N)break;
		if(distancia[po]>jump){
				distancia[po]=jum;
				//cout<<distancia[po]<<' '<<po<<' ';
				for(int i=0;i<M;i++)if(doge[i].first==po)q.push(make_pair(doge[i],jum));
			}
	}
}
cout<<distancia[1];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -