oj.uz

Submission #45213

# Submission time Handle Problem Language Result Execution time Memory
45213 2018-04-11T21:30:36 Z ckodser Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 221 ms 217724 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=3e4+10;
const ll mod=1e9+7;
const ll inf=1e9+500;
const ll rad=100;
const ll maxm=maxn*(rad)*3+50;

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

ll cn;
vector<pair<ll,bool> > ger[maxm];
bitset<maxm> h;


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));
		}
	}

	cn=m+n*2*rad;

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




	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]){
			if(v==1){
				cout<<w-1;
				return 0;
			}
			h[v]=1;
			for(auto e:ger[v]){
				if(e.S){
					dk.push_back(mp(e.F,w+1));
				}else{
					dk.push_front(mp(e.F,w));
				}
			}
		}
	}
	cout<<-1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 212472 KB Output is correct
2 Correct 184 ms 212516 KB Output is correct
3 Correct 167 ms 212588 KB Output is correct
4 Correct 163 ms 212588 KB Output is correct
5 Correct 166 ms 212712 KB Output is correct
6 Correct 165 ms 212712 KB Output is correct
7 Correct 169 ms 212712 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 212712 KB Output is correct
2 Correct 163 ms 212712 KB Output is correct
3 Correct 162 ms 212712 KB Output is correct
4 Correct 185 ms 212712 KB Output is correct
5 Correct 168 ms 212712 KB Output is correct
6 Correct 170 ms 212712 KB Output is correct
7 Correct 167 ms 212712 KB Output is correct
8 Correct 166 ms 212820 KB Output is correct
9 Correct 166 ms 213040 KB Output is correct
10 Correct 164 ms 213296 KB Output is correct
11 Correct 169 ms 213424 KB Output is correct
12 Correct 166 ms 213520 KB Output is correct
13 Correct 169 ms 213600 KB Output is correct
14 Correct 168 ms 213600 KB Output is correct
15 Correct 170 ms 213600 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 213600 KB Output is correct
2 Correct 164 ms 213600 KB Output is correct
3 Correct 167 ms 213600 KB Output is correct
4 Correct 166 ms 213600 KB Output is correct
5 Correct 172 ms 213600 KB Output is correct
6 Correct 221 ms 213600 KB Output is correct
7 Correct 166 ms 213600 KB Output is correct
8 Correct 170 ms 213600 KB Output is correct
9 Correct 171 ms 213600 KB Output is correct
10 Correct 169 ms 213600 KB Output is correct
11 Correct 177 ms 213600 KB Output is correct
12 Correct 171 ms 213628 KB Output is correct
13 Correct 167 ms 213628 KB Output is correct
14 Correct 169 ms 213628 KB Output is correct
15 Correct 182 ms 213628 KB Output is correct
16 Correct 169 ms 214200 KB Output is correct
17 Incorrect 189 ms 217724 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 217724 KB Output is correct
2 Correct 163 ms 217724 KB Output is correct
3 Correct 165 ms 217724 KB Output is correct
4 Correct 168 ms 217724 KB Output is correct
5 Correct 174 ms 217724 KB Output is correct
6 Correct 177 ms 217724 KB Output is correct
7 Correct 167 ms 217724 KB Output is correct
8 Correct 184 ms 217724 KB Output is correct
9 Correct 169 ms 217724 KB Output is correct
10 Correct 173 ms 217724 KB Output is correct
11 Correct 167 ms 217724 KB Output is correct
12 Correct 203 ms 217724 KB Output is correct
13 Correct 188 ms 217724 KB Output is correct
14 Correct 171 ms 217724 KB Output is correct
15 Correct 175 ms 217724 KB Output is correct
16 Correct 176 ms 217724 KB Output is correct
17 Incorrect 186 ms 217724 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 217724 KB Output is correct
2 Correct 163 ms 217724 KB Output is correct
3 Correct 220 ms 217724 KB Output is correct
4 Correct 165 ms 217724 KB Output is correct
5 Correct 163 ms 217724 KB Output is correct
6 Correct 167 ms 217724 KB Output is correct
7 Correct 169 ms 217724 KB Output is correct
8 Correct 165 ms 217724 KB Output is correct
9 Correct 168 ms 217724 KB Output is correct
10 Correct 168 ms 217724 KB Output is correct
11 Correct 169 ms 217724 KB Output is correct
12 Correct 172 ms 217724 KB Output is correct
13 Correct 174 ms 217724 KB Output is correct
14 Correct 187 ms 217724 KB Output is correct
15 Correct 165 ms 217724 KB Output is correct
16 Correct 169 ms 217724 KB Output is correct
17 Incorrect 185 ms 217724 KB Output isn't correct
18 Halted 0 ms 0 KB -