oj.uz

Submission #45208

# Submission time Handle Problem Language Result Execution time Memory
45208 2018-04-11T21:11:28 Z ckodser Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 1000 ms 262144 KB 
#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]));
			}	
		}		
	}
	deque<pii> dk;
	dk.pb(mp(1,0));
	while(dk.size()){
		ll v=dk.front().S;
		ll w=dk.front().F;
		dk.pop_front();
		if(h[v]==0){
			h[v]=w;
			for(auto e:ger[v]){
				if(e.S){
					dk.pb(mp(w+1,e.F));
				}else{
					dk.push_front(mp(w,e.F));
				}
			}
		}
	}
	/*
	   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

# Verdict Execution time Memory Grader output
1 Correct 149 ms 190712 KB Output is correct
2 Correct 173 ms 190712 KB Output is correct
3 Correct 155 ms 190896 KB Output is correct
4 Correct 149 ms 191096 KB Output is correct
5 Correct 150 ms 191552 KB Output is correct
6 Correct 152 ms 191552 KB Output is correct
7 Correct 148 ms 191552 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 191552 KB Output is correct
2 Correct 162 ms 191552 KB Output is correct
3 Correct 150 ms 191552 KB Output is correct
4 Correct 200 ms 191552 KB Output is correct
5 Correct 149 ms 191688 KB Output is correct
6 Correct 148 ms 191688 KB Output is correct
7 Correct 147 ms 191784 KB Output is correct
8 Correct 159 ms 195068 KB Output is correct
9 Correct 162 ms 197884 KB Output is correct
10 Correct 179 ms 203132 KB Output is correct
11 Correct 180 ms 203256 KB Output is correct
12 Correct 173 ms 203256 KB Output is correct
13 Correct 174 ms 203256 KB Output is correct
14 Correct 174 ms 203256 KB Output is correct
15 Correct 175 ms 203256 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 203256 KB Output is correct
2 Correct 147 ms 203256 KB Output is correct
3 Correct 262 ms 203256 KB Output is correct
4 Correct 152 ms 203256 KB Output is correct
5 Correct 155 ms 203256 KB Output is correct
6 Correct 149 ms 203256 KB Output is correct
7 Correct 148 ms 203256 KB Output is correct
8 Correct 158 ms 203256 KB Output is correct
9 Correct 163 ms 203256 KB Output is correct
10 Correct 173 ms 203256 KB Output is correct
11 Correct 173 ms 203256 KB Output is correct
12 Correct 172 ms 203256 KB Output is correct
13 Correct 174 ms 203292 KB Output is correct
14 Correct 177 ms 203292 KB Output is correct
15 Correct 174 ms 203292 KB Output is correct
16 Correct 214 ms 215672 KB Output is correct
17 Execution timed out 1085 ms 262144 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 262144 KB Output is correct
2 Correct 149 ms 262144 KB Output is correct
3 Correct 154 ms 262144 KB Output is correct
4 Correct 162 ms 262144 KB Output is correct
5 Correct 155 ms 262144 KB Output is correct
6 Correct 149 ms 262144 KB Output is correct
7 Correct 149 ms 262144 KB Output is correct
8 Correct 159 ms 262144 KB Output is correct
9 Correct 168 ms 262144 KB Output is correct
10 Correct 188 ms 262144 KB Output is correct
11 Correct 180 ms 262144 KB Output is correct
12 Correct 178 ms 262144 KB Output is correct
13 Correct 183 ms 262144 KB Output is correct
14 Correct 187 ms 262144 KB Output is correct
15 Correct 183 ms 262144 KB Output is correct
16 Correct 215 ms 262144 KB Output is correct
17 Execution timed out 1105 ms 262144 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 262144 KB Output is correct
2 Correct 147 ms 262144 KB Output is correct
3 Correct 150 ms 262144 KB Output is correct
4 Correct 152 ms 262144 KB Output is correct
5 Correct 152 ms 262144 KB Output is correct
6 Correct 151 ms 262144 KB Output is correct
7 Correct 149 ms 262144 KB Output is correct
8 Correct 162 ms 262144 KB Output is correct
9 Correct 204 ms 262144 KB Output is correct
10 Correct 179 ms 262144 KB Output is correct
11 Correct 206 ms 262144 KB Output is correct
12 Correct 182 ms 262144 KB Output is correct
13 Correct 193 ms 262144 KB Output is correct
14 Correct 181 ms 262144 KB Output is correct
15 Correct 180 ms 262144 KB Output is correct
16 Correct 245 ms 262144 KB Output is correct
17 Execution timed out 1110 ms 262144 KB Time limit exceeded
18 Halted 0 ms 0 KB -