Submission #68798

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
68798	2018-08-18T13:45:05 Z	FedericoS	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	6 ms	3220 KB

skyscraper

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
typedef pair<int,pair<int,int>> pp;

int N,M;
int B[30005],P[30005];
vector<int> V[30005];
deque<pp> Q;

int main(){

	cin>>N>>M;
	for(int i=0;i<M;i++){
		cin>>B[i]>>P[i];
		if(i)
			V[B[i]].push_back(i);
	}

	//indice distanza posizione

	Q.push_back({0,{0,B[0]}});

	while(!Q.empty()){

		pp p=Q.front();
		Q.pop_front();

		//cout<<Q.size()<<" "<<p.first<<" "<<p.second.first<<" "<<p.second.second<<endl;

		if(p.first==1){
			cout<<p.second.first;
			return 0;
		}

		for(int x:V[p.second.second])
			Q.push_front({x,{p.second.first,B[x]}});
		V[p.second.second].clear();

		if(p.second.second==B[p.first]){
			if(p.second.second-P[p.first]>=0)
				Q.push_back({p.first,{p.second.first+1,p.second.second-P[p.first]}});
			if(p.second.second+P[p.first]<N)
				Q.push_back({p.first,{p.second.first+1,p.second.second+P[p.first]}});
		}

		if(p.second.second<B[p.first]){
			if(p.second.second-P[p.first]>=0)
				Q.push_back({p.first,{p.second.first+1,p.second.second-P[p.first]}});
		}

		if(p.second.second>B[p.first]){
			if(p.second.second+P[p.first]>=0)
				Q.push_back({p.first,{p.second.first+1,p.second.second+P[p.first]}});
		}

	}

	cout<<-1;

}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1148 KB	Output is correct
2	Correct	5 ms	1252 KB	Output is correct
3	Correct	4 ms	1308 KB	Output is correct
4	Correct	4 ms	1356 KB	Output is correct
5	Correct	4 ms	1392 KB	Output is correct
6	Correct	3 ms	1440 KB	Output is correct
7	Correct	3 ms	1444 KB	Output is correct

Subtask #2

12.0 / 12.0

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

Subtask #3

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1844 KB	Output is correct
2	Correct	3 ms	1844 KB	Output is correct
3	Correct	4 ms	1844 KB	Output is correct
4	Correct	4 ms	1844 KB	Output is correct
5	Correct	4 ms	1844 KB	Output is correct
6	Correct	4 ms	1844 KB	Output is correct
7	Correct	4 ms	1844 KB	Output is correct
8	Correct	3 ms	1844 KB	Output is correct
9	Correct	5 ms	1844 KB	Output is correct
10	Correct	4 ms	1844 KB	Output is correct
11	Correct	4 ms	1844 KB	Output is correct
12	Correct	4 ms	1852 KB	Output is correct
13	Correct	5 ms	1964 KB	Output is correct
14	Correct	5 ms	1964 KB	Output is correct
15	Correct	6 ms	1964 KB	Output is correct
16	Correct	3 ms	1964 KB	Output is correct
17	Correct	6 ms	1964 KB	Output is correct
18	Runtime error	6 ms	2836 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2836 KB	Output is correct
2	Correct	3 ms	2836 KB	Output is correct
3	Correct	3 ms	2836 KB	Output is correct
4	Correct	3 ms	2864 KB	Output is correct
5	Correct	3 ms	2864 KB	Output is correct
6	Correct	3 ms	2864 KB	Output is correct
7	Correct	3 ms	2864 KB	Output is correct
8	Correct	4 ms	2864 KB	Output is correct
9	Correct	3 ms	2864 KB	Output is correct
10	Correct	4 ms	2864 KB	Output is correct
11	Correct	5 ms	2864 KB	Output is correct
12	Correct	5 ms	2916 KB	Output is correct
13	Correct	6 ms	2920 KB	Output is correct
14	Correct	6 ms	2920 KB	Output is correct
15	Correct	4 ms	2920 KB	Output is correct
16	Correct	5 ms	2920 KB	Output is correct
17	Correct	5 ms	2964 KB	Output is correct
18	Runtime error	6 ms	2992 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2992 KB	Output is correct
2	Correct	4 ms	2992 KB	Output is correct
3	Correct	4 ms	2992 KB	Output is correct
4	Correct	4 ms	2992 KB	Output is correct
5	Correct	3 ms	2992 KB	Output is correct
6	Correct	4 ms	2992 KB	Output is correct
7	Correct	4 ms	2992 KB	Output is correct
8	Correct	3 ms	2992 KB	Output is correct
9	Correct	4 ms	2992 KB	Output is correct
10	Correct	5 ms	2992 KB	Output is correct
11	Correct	5 ms	2992 KB	Output is correct
12	Correct	6 ms	3068 KB	Output is correct
13	Correct	5 ms	3080 KB	Output is correct
14	Correct	6 ms	3220 KB	Output is correct
15	Correct	5 ms	3220 KB	Output is correct
16	Correct	5 ms	3220 KB	Output is correct
17	Correct	5 ms	3220 KB	Output is correct
18	Runtime error	6 ms	3220 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Halted	0 ms	0 KB	-