답안 #45206 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45206	2018-04-11T21:08:05 Z	ckodser	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	1000 ms	262144 KB

skyscraper

#include<bits/stdc++.h>

#define ll	int 
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=2010;
const ll mod=1e9+7;
const ll inf=1e9+500;
const ll rad=2010;
const ll maxm=maxn*(rad)*2+50;

ll b[maxn];
ll p[maxn];
vector<ll> vec[maxn];

vector<pair<ll,short> > ger[maxm];
ll h[maxm];


int main(){

	ll n,m;
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		cin>>b[i]>>p[i];
		vec[b[i]].pb(i);
	}
	for(ll i=0;i<n;i++){
		for(auto v:vec[i]){
			ger[i+m].pb(mp(v,0));
		}
	}	

	
	for(ll j=1;j<rad;j++){
		for(ll i=0;i<n;i++){
			ger[m+j*n+i].pb(mp(i+m,0));
			if(i>=j){
				ger[m+j*n+i].pb(mp(m+j*n+i-j,1));
			}
		}
	}
	for(ll j=1;j<rad;j++){
		for(ll i=0;i<n;i++){
			ll v=m+rad*n+(j-1)*n+i;
			ger[v].pb(mp(i+m,0));
			if(i+j<n){
				ger[v].pb(mp(v+j,1));
			}
		}
	}
	for(ll i=0;i<m;i++){
		if(p[i]<rad){
			ll v=b[i];
			ger[i].pb(mp(m+n*p[i]+v,0));
			ger[i].pb(mp(m+rad*n+(p[i]-1)*n+v,0));
		}
	}

	for(ll i=0;i<m;i++){
		if(p[i]>=rad){
			for(ll j=b[i]+p[i];j<n;j+=p[i]){
				ger[i].pb(mp(j+m,(j-b[i])/p[i]));
			}
			for(ll j=b[i]-p[i];j>=0;j-=p[i]){
				ger[i].pb(mp(j+m,(b[i]-j)/p[i]));
			}	
		}		
	}

	set<pii> st;
	set<pii> :: iterator it;
	st.insert(mp(1,0));
	while(st.size()){
		it=st.begin();
		ll v=(*it).S;
		ll w=(*it).F;
		st.erase(it);
		if(h[v]==0){
			h[v]=w;
			for(auto e:ger[v]){
				st.insert(mp(e.S+w,e.F));
			}
		}
	}
	if(h[1]==0){
		cout<<-1;
	}else{
		cout<<h[1]-1;
	}
}
/*    
	  .      _______    __    ___     ________      ________       _________     _________   ________
	  .     /       \  |  |  /  /    /        \    |        \     /         \   |        |  |   __   \
	  .    /   _____/  |  | /  /    /    ___   \   |   ___   \   |   _______/   |  ______|  |  |  \   \
	  .   /   /        |  |/  /    /    /   \   \  |  |   \   \  |  (______     |  |_____   |  |__/   /
	  .   |  |         |     /     |   /     \  |  |  |    |  |   \        \    |        |  |      __/
	  .   |  |         |     \     |   \     /  |  |  |    |  |    \______  \   |  ______|  |      \
	  .   \   \_____   |  |\  \    \    \___/   /  |  |___/   /    _______) |   |  |_____   |   |\  \
	  .    \        \  |  | \  \    \          /   |         /    /         /   |        |  |   | \  \
	  .     \_______/  |__|  \__\    \________/    |________/     \________/    |________|  |___|  \__\
 */

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	158 ms	190840 KB	Output is correct
2	Correct	145 ms	190840 KB	Output is correct
3	Correct	167 ms	191020 KB	Output is correct
4	Correct	168 ms	191300 KB	Output is correct
5	Correct	173 ms	191528 KB	Output is correct
6	Correct	155 ms	191784 KB	Output is correct
7	Correct	157 ms	191784 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	191784 KB	Output is correct
2	Correct	177 ms	191784 KB	Output is correct
3	Correct	176 ms	191784 KB	Output is correct
4	Correct	186 ms	191784 KB	Output is correct
5	Correct	204 ms	191784 KB	Output is correct
6	Correct	181 ms	191784 KB	Output is correct
7	Correct	188 ms	191784 KB	Output is correct
8	Correct	175 ms	195044 KB	Output is correct
9	Correct	182 ms	197860 KB	Output is correct
10	Correct	210 ms	203108 KB	Output is correct
11	Correct	183 ms	203200 KB	Output is correct
12	Correct	190 ms	203236 KB	Output is correct
13	Correct	174 ms	203236 KB	Output is correct
14	Correct	183 ms	203356 KB	Output is correct
15	Correct	192 ms	203356 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	148 ms	203356 KB	Output is correct
2	Correct	155 ms	203356 KB	Output is correct
3	Correct	160 ms	203356 KB	Output is correct
4	Correct	150 ms	203356 KB	Output is correct
5	Correct	186 ms	203356 KB	Output is correct
6	Correct	148 ms	203356 KB	Output is correct
7	Correct	165 ms	203356 KB	Output is correct
8	Correct	170 ms	203356 KB	Output is correct
9	Correct	171 ms	203356 KB	Output is correct
10	Correct	180 ms	203356 KB	Output is correct
11	Correct	180 ms	203356 KB	Output is correct
12	Correct	177 ms	203356 KB	Output is correct
13	Correct	177 ms	203356 KB	Output is correct
14	Correct	225 ms	203356 KB	Output is correct
15	Correct	179 ms	203356 KB	Output is correct
16	Correct	211 ms	215548 KB	Output is correct
17	Execution timed out	1095 ms	262144 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	213 ms	262144 KB	Output is correct
2	Correct	178 ms	262144 KB	Output is correct
3	Correct	203 ms	262144 KB	Output is correct
4	Correct	174 ms	262144 KB	Output is correct
5	Correct	155 ms	262144 KB	Output is correct
6	Correct	176 ms	262144 KB	Output is correct
7	Correct	150 ms	262144 KB	Output is correct
8	Correct	160 ms	262144 KB	Output is correct
9	Correct	168 ms	262144 KB	Output is correct
10	Correct	182 ms	262144 KB	Output is correct
11	Correct	204 ms	262144 KB	Output is correct
12	Correct	190 ms	262144 KB	Output is correct
13	Correct	215 ms	262144 KB	Output is correct
14	Correct	176 ms	262144 KB	Output is correct
15	Correct	180 ms	262144 KB	Output is correct
16	Correct	222 ms	262144 KB	Output is correct
17	Execution timed out	1109 ms	262144 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	182 ms	262144 KB	Output is correct
2	Correct	164 ms	262144 KB	Output is correct
3	Correct	175 ms	262144 KB	Output is correct
4	Correct	182 ms	262144 KB	Output is correct
5	Correct	187 ms	262144 KB	Output is correct
6	Correct	155 ms	262144 KB	Output is correct
7	Correct	168 ms	262144 KB	Output is correct
8	Correct	179 ms	262144 KB	Output is correct
9	Correct	195 ms	262144 KB	Output is correct
10	Correct	197 ms	262144 KB	Output is correct
11	Correct	230 ms	262144 KB	Output is correct
12	Correct	193 ms	262144 KB	Output is correct
13	Correct	193 ms	262144 KB	Output is correct
14	Correct	198 ms	262144 KB	Output is correct
15	Correct	193 ms	262144 KB	Output is correct
16	Correct	220 ms	262144 KB	Output is correct
17	Execution timed out	1116 ms	262144 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

답안 #45206

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 14.0

Subtask #4 0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0