oj.uz

Submission #45206

# Submission time Handle Problem Language Result Execution time Memory
45206 2018-04-11T21:08:05 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]));
			}	
		}		
	}

	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 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -