oj.uz

Submission #45204

# Submission time Handle Problem Language Result Execution time Memory
45204 2018-04-11T20:43:45 Z ckodser Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 161 ms 149808 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=30010;
const ll mod=1e9+7;
const ll inf=1e9+500;
const ll rad=100;
const ll maxm=maxn*(rad+1)*2+5;

ll b[maxn];
ll p[maxn];
vector<ll> vec[maxn];
vector<pair<ll,bool> > 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 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,1));
			}
			for(ll j=b[i]-p[i];j>=0;j-=p[i]){
				ger[i].pb(mp(j+m,1));
			}	
		}		
	}
	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));
		}
	}






	deque<pii>dk;
	dk.pb(mp(0,1));
	while(dk.size()){
		ll v=dk.front().F;
		ll w=dk.front().S;
		dk.pop_front();
		if(h[v]==0){
			h[v]=w;
			for(auto e:ger[v]){
				if(e.S){
					dk.push_back(mp(e.F,w+1));
				}else{
					dk.push_front(mp(e.F,w));
				}
			}
		}
	}
	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 121 ms 143444 KB Output is correct
2 Correct 116 ms 143496 KB Output is correct
3 Correct 115 ms 143532 KB Output is correct
4 Correct 119 ms 143752 KB Output is correct
5 Correct 114 ms 143752 KB Output is correct
6 Correct 113 ms 143780 KB Output is correct
7 Correct 134 ms 143788 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 143788 KB Output is correct
2 Correct 113 ms 143788 KB Output is correct
3 Correct 115 ms 143848 KB Output is correct
4 Correct 112 ms 143848 KB Output is correct
5 Correct 114 ms 143864 KB Output is correct
6 Correct 132 ms 143908 KB Output is correct
7 Correct 115 ms 143908 KB Output is correct
8 Correct 113 ms 144084 KB Output is correct
9 Correct 117 ms 144136 KB Output is correct
10 Correct 117 ms 144664 KB Output is correct
11 Correct 117 ms 144672 KB Output is correct
12 Correct 120 ms 144764 KB Output is correct
13 Correct 117 ms 144764 KB Output is correct
14 Correct 120 ms 144764 KB Output is correct
15 Correct 117 ms 144768 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 144768 KB Output is correct
2 Correct 118 ms 144768 KB Output is correct
3 Correct 116 ms 144768 KB Output is correct
4 Correct 115 ms 144768 KB Output is correct
5 Correct 115 ms 144768 KB Output is correct
6 Correct 112 ms 144768 KB Output is correct
7 Correct 115 ms 144768 KB Output is correct
8 Correct 116 ms 144768 KB Output is correct
9 Correct 126 ms 144768 KB Output is correct
10 Correct 134 ms 144820 KB Output is correct
11 Correct 118 ms 144824 KB Output is correct
12 Correct 136 ms 144852 KB Output is correct
13 Correct 121 ms 144852 KB Output is correct
14 Correct 118 ms 145004 KB Output is correct
15 Correct 119 ms 145004 KB Output is correct
16 Correct 118 ms 145284 KB Output is correct
17 Incorrect 134 ms 149416 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 149416 KB Output is correct
2 Correct 112 ms 149416 KB Output is correct
3 Correct 113 ms 149416 KB Output is correct
4 Correct 114 ms 149416 KB Output is correct
5 Correct 120 ms 149416 KB Output is correct
6 Correct 114 ms 149416 KB Output is correct
7 Correct 114 ms 149416 KB Output is correct
8 Correct 119 ms 149416 KB Output is correct
9 Correct 124 ms 149416 KB Output is correct
10 Correct 115 ms 149416 KB Output is correct
11 Correct 116 ms 149416 KB Output is correct
12 Correct 116 ms 149416 KB Output is correct
13 Correct 119 ms 149416 KB Output is correct
14 Correct 119 ms 149416 KB Output is correct
15 Correct 118 ms 149416 KB Output is correct
16 Correct 117 ms 149416 KB Output is correct
17 Incorrect 161 ms 149512 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 149512 KB Output is correct
2 Correct 116 ms 149512 KB Output is correct
3 Correct 113 ms 149512 KB Output is correct
4 Correct 115 ms 149512 KB Output is correct
5 Correct 113 ms 149512 KB Output is correct
6 Correct 128 ms 149512 KB Output is correct
7 Correct 139 ms 149512 KB Output is correct
8 Correct 115 ms 149512 KB Output is correct
9 Correct 115 ms 149512 KB Output is correct
10 Correct 116 ms 149512 KB Output is correct
11 Correct 116 ms 149512 KB Output is correct
12 Correct 119 ms 149512 KB Output is correct
13 Correct 119 ms 149512 KB Output is correct
14 Correct 120 ms 149512 KB Output is correct
15 Correct 129 ms 149512 KB Output is correct
16 Correct 118 ms 149512 KB Output is correct
17 Incorrect 141 ms 149808 KB Output isn't correct
18 Halted 0 ms 0 KB -