oj.uz

Submission #162663

# Submission time Handle Problem Language Result Execution time Memory
162663 2019-11-09T07:42:15 Z HungAnhGoldIBO2020 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 772 ms 262148 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
const int N=3e4;
const int inf=1e9+7;
const int LIM=N*174;
vector<int> lis[N<<1];
int b[N],p[N],dis[LIM],lst[N];
bool ok[N];
vector<pair<int,int> > adj[LIM];
//priority_queue<pair<int,int> > lis;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,i,j,k,l=0;
	cin>>n>>m;
	for(i=0;i<m;i++){		//0->m-1
		cin>>b[i]>>p[i];
		if(ok[b[i]]){
			adj[i].push_back({lst[b[i]],0});
		}
		l=max(l,p[i]);
		lst[b[i]]=i;
		ok[b[i]]=true;
	}
	int magic=sqrt(l)+1;
	int lim=min(magic,n-1);
	//m -> m+(n-1)*magic la cac nut dai dien cho cac luong van tai
	for(i=1;i<=lim;++i){
		for(j=0;j<n-i;++j){
			k=(i-1)*n+j+m;
			l=(i-1)*n+j+i+m;
			adj[k].push_back({l,1});
			adj[l].push_back({k,1});
		}
	}
	for(i=0;i<m;++i){
		if(i==lst[b[i]]){
			for(j=1;j<=lim;++j){
				k=(j-1)*n+b[i]+m;
				adj[k].push_back({i,0});
			}
		}		
		if(p[i]>lim){
			j=b[i];
			k=0;
			while(j>=0){
				if(ok[j]){
					adj[i].push_back({lst[j],k});
				}
				j-=p[i];
				++k;
			}
			j=b[i];
			k=0;
			while(j+p[i]<n){
				j+=p[i];
				++k;
				if(ok[j]){
					adj[i].push_back({lst[j],k});
				}
			}
		}		//the dog, not the dai dien :'(
		else{
			k=(p[i]-1)*n+b[i]+m;
			adj[i].push_back({k,0});
		}
	}
	fill(dis+1,dis+LIM,inf);
//	lis.push({0,0});
//	while(lis.size()){
//		j=-lis.top().first;
//		k=lis.top().second;
//		lis.pop();
//		if(dis[k]==j){
//			for(i=0;i<adj[k].size();++i){
//				if(dis[adj[k][i].first]>dis[k]+adj[k][i].second){
//					dis[adj[k][i].first]=dis[k]+adj[k][i].second;
//					lis.push({-dis[adj[k][i].first],adj[k][i].first});
//				}
//			}
//		}
//	}
	int cnt=1;
	lis[dis[0]].push_back(0);
	for(i=0;i<LIM&&cnt;++i){
		while(lis[i].size()){
			j=lis[i].back();
			--cnt;
			lis[i].pop_back();
			if(dis[j]!=i){
				continue;
			}
			for(k=0;k<adj[j].size();++k){
				if(dis[adj[j][k].first]>dis[j]+adj[j][k].second){
					dis[adj[j][k].first]=dis[j]+adj[j][k].second;
					lis[dis[adj[j][k].first]].push_back(adj[j][k].first);
					++cnt;
				}
			}
		}
	}
	if(dis[1]!=inf){
		cout<<dis[1];
	}
	else{
		cout<<-1;
	}
}
/*
5 3
0 2
1 1
4 1
*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:95:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(k=0;k<adj[j].size();++k){
            ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 144732 KB Output is correct
2 Correct 131 ms 144732 KB Output is correct
3 Correct 130 ms 144760 KB Output is correct
4 Correct 131 ms 144888 KB Output is correct
5 Correct 131 ms 144888 KB Output is correct
6 Correct 137 ms 144824 KB Output is correct
7 Correct 132 ms 144732 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 144852 KB Output is correct
2 Correct 131 ms 144884 KB Output is correct
3 Correct 131 ms 144760 KB Output is correct
4 Correct 132 ms 144760 KB Output is correct
5 Correct 130 ms 144760 KB Output is correct
6 Correct 148 ms 144760 KB Output is correct
7 Correct 141 ms 144780 KB Output is correct
8 Correct 151 ms 144760 KB Output is correct
9 Correct 141 ms 144888 KB Output is correct
10 Correct 136 ms 144888 KB Output is correct
11 Correct 133 ms 145016 KB Output is correct
12 Correct 133 ms 144888 KB Output is correct
13 Correct 132 ms 144888 KB Output is correct
14 Correct 141 ms 144912 KB Output is correct
15 Correct 133 ms 144976 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 144792 KB Output is correct
2 Correct 131 ms 144836 KB Output is correct
3 Correct 131 ms 144788 KB Output is correct
4 Correct 134 ms 144760 KB Output is correct
5 Correct 131 ms 144756 KB Output is correct
6 Correct 133 ms 144916 KB Output is correct
7 Correct 133 ms 144732 KB Output is correct
8 Correct 135 ms 144760 KB Output is correct
9 Correct 132 ms 144764 KB Output is correct
10 Correct 134 ms 145016 KB Output is correct
11 Correct 135 ms 145100 KB Output is correct
12 Correct 147 ms 144860 KB Output is correct
13 Correct 133 ms 144888 KB Output is correct
14 Correct 146 ms 144960 KB Output is correct
15 Correct 134 ms 145020 KB Output is correct
16 Correct 137 ms 145048 KB Output is correct
17 Correct 157 ms 145784 KB Output is correct
18 Correct 169 ms 148408 KB Output is correct
19 Correct 157 ms 148472 KB Output is correct
20 Correct 151 ms 145128 KB Output is correct
21 Correct 156 ms 145784 KB Output is correct
22 Correct 165 ms 148216 KB Output is correct
23 Correct 156 ms 148216 KB Output is correct
24 Correct 160 ms 149144 KB Output is correct
25 Correct 157 ms 149212 KB Output is correct
26 Correct 136 ms 145912 KB Output is correct
27 Correct 146 ms 147832 KB Output is correct
28 Correct 176 ms 150044 KB Output is correct
29 Correct 132 ms 145400 KB Output is correct
30 Correct 133 ms 145264 KB Output is correct
31 Correct 135 ms 145272 KB Output is correct
32 Correct 149 ms 145400 KB Output is correct
33 Correct 136 ms 145656 KB Output is correct
34 Correct 136 ms 145528 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 144764 KB Output is correct
2 Correct 137 ms 144788 KB Output is correct
3 Correct 132 ms 144864 KB Output is correct
4 Correct 134 ms 144704 KB Output is correct
5 Correct 132 ms 144760 KB Output is correct
6 Correct 139 ms 144800 KB Output is correct
7 Correct 136 ms 144716 KB Output is correct
8 Correct 137 ms 144732 KB Output is correct
9 Correct 139 ms 144880 KB Output is correct
10 Correct 141 ms 144900 KB Output is correct
11 Correct 152 ms 145032 KB Output is correct
12 Correct 139 ms 144888 KB Output is correct
13 Correct 135 ms 144888 KB Output is correct
14 Correct 141 ms 144988 KB Output is correct
15 Correct 139 ms 145016 KB Output is correct
16 Correct 133 ms 145016 KB Output is correct
17 Correct 151 ms 146088 KB Output is correct
18 Correct 155 ms 148368 KB Output is correct
19 Correct 166 ms 148436 KB Output is correct
20 Correct 152 ms 145160 KB Output is correct
21 Correct 157 ms 146028 KB Output is correct
22 Correct 166 ms 148216 KB Output is correct
23 Correct 157 ms 148216 KB Output is correct
24 Correct 170 ms 149040 KB Output is correct
25 Correct 171 ms 149324 KB Output is correct
26 Correct 144 ms 146012 KB Output is correct
27 Correct 147 ms 147916 KB Output is correct
28 Correct 176 ms 149992 KB Output is correct
29 Correct 134 ms 145404 KB Output is correct
30 Correct 134 ms 145400 KB Output is correct
31 Correct 141 ms 145332 KB Output is correct
32 Correct 140 ms 145348 KB Output is correct
33 Correct 153 ms 145632 KB Output is correct
34 Correct 135 ms 145632 KB Output is correct
35 Correct 176 ms 150400 KB Output is correct
36 Correct 154 ms 147800 KB Output is correct
37 Correct 178 ms 150744 KB Output is correct
38 Correct 222 ms 152876 KB Output is correct
39 Correct 196 ms 152568 KB Output is correct
40 Correct 201 ms 152688 KB Output is correct
41 Correct 202 ms 152592 KB Output is correct
42 Correct 146 ms 147432 KB Output is correct
43 Correct 169 ms 149112 KB Output is correct
44 Correct 159 ms 146308 KB Output is correct
45 Correct 164 ms 147768 KB Output is correct
46 Correct 175 ms 147832 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 144792 KB Output is correct
2 Correct 149 ms 144760 KB Output is correct
3 Correct 147 ms 144752 KB Output is correct
4 Correct 139 ms 144760 KB Output is correct
5 Correct 138 ms 144812 KB Output is correct
6 Correct 145 ms 144784 KB Output is correct
7 Correct 150 ms 144776 KB Output is correct
8 Correct 142 ms 144852 KB Output is correct
9 Correct 150 ms 144836 KB Output is correct
10 Correct 150 ms 145016 KB Output is correct
11 Correct 151 ms 144996 KB Output is correct
12 Correct 150 ms 144868 KB Output is correct
13 Correct 149 ms 145052 KB Output is correct
14 Correct 138 ms 145016 KB Output is correct
15 Correct 136 ms 145016 KB Output is correct
16 Correct 136 ms 145016 KB Output is correct
17 Correct 151 ms 145888 KB Output is correct
18 Correct 163 ms 148532 KB Output is correct
19 Correct 149 ms 148600 KB Output is correct
20 Correct 134 ms 145144 KB Output is correct
21 Correct 151 ms 145908 KB Output is correct
22 Correct 161 ms 148344 KB Output is correct
23 Correct 167 ms 148216 KB Output is correct
24 Correct 160 ms 149056 KB Output is correct
25 Correct 157 ms 149212 KB Output is correct
26 Correct 136 ms 146040 KB Output is correct
27 Correct 142 ms 147920 KB Output is correct
28 Correct 238 ms 150092 KB Output is correct
29 Correct 133 ms 145400 KB Output is correct
30 Correct 135 ms 145272 KB Output is correct
31 Correct 144 ms 145288 KB Output is correct
32 Correct 141 ms 145324 KB Output is correct
33 Correct 153 ms 145588 KB Output is correct
34 Correct 172 ms 145560 KB Output is correct
35 Correct 182 ms 150188 KB Output is correct
36 Correct 154 ms 147832 KB Output is correct
37 Correct 184 ms 150580 KB Output is correct
38 Correct 220 ms 152376 KB Output is correct
39 Correct 211 ms 152312 KB Output is correct
40 Correct 198 ms 152440 KB Output is correct
41 Correct 222 ms 152396 KB Output is correct
42 Correct 153 ms 147036 KB Output is correct
43 Correct 155 ms 148984 KB Output is correct
44 Correct 148 ms 146144 KB Output is correct
45 Correct 158 ms 147576 KB Output is correct
46 Correct 167 ms 147732 KB Output is correct
47 Correct 700 ms 184228 KB Output is correct
48 Runtime error 772 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Halted 0 ms 0 KB -