oj.uz

Submission #162655

# Submission time Handle Problem Language Result Execution time Memory
162655 2019-11-09T07:27:49 Z HungAnhGoldIBO2020 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 200084 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+2;
const int magic=120;
const int inf=1e9+7;
const int LIM=N*magic;
vector<int> lis[N*10];
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;
	cin>>n>>m;
	int lim=min(magic,n-1);
	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});
		}
		lst[b[i]]=i;
		ok[b[i]]=true;
	}
	//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){
		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;
					cnt++;
					lis[dis[adj[j][k].first]].push_back(adj[j][k].first);
				}
			}
		}
	}
	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:92: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 97 ms 106104 KB Output is correct
2 Correct 110 ms 106104 KB Output is correct
3 Correct 98 ms 106024 KB Output is correct
4 Correct 98 ms 106104 KB Output is correct
5 Correct 97 ms 105992 KB Output is correct
6 Correct 96 ms 106104 KB Output is correct
7 Correct 97 ms 106108 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 106104 KB Output is correct
2 Correct 99 ms 105976 KB Output is correct
3 Correct 97 ms 106104 KB Output is correct
4 Correct 99 ms 105976 KB Output is correct
5 Correct 99 ms 105960 KB Output is correct
6 Correct 97 ms 106232 KB Output is correct
7 Correct 97 ms 105976 KB Output is correct
8 Correct 97 ms 106108 KB Output is correct
9 Correct 146 ms 106172 KB Output is correct
10 Correct 104 ms 106744 KB Output is correct
11 Correct 113 ms 108664 KB Output is correct
12 Correct 103 ms 108028 KB Output is correct
13 Correct 106 ms 108236 KB Output is correct
14 Correct 110 ms 108536 KB Output is correct
15 Correct 122 ms 108664 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 106016 KB Output is correct
2 Correct 110 ms 105976 KB Output is correct
3 Correct 109 ms 105976 KB Output is correct
4 Correct 104 ms 106020 KB Output is correct
5 Correct 98 ms 106104 KB Output is correct
6 Correct 110 ms 106224 KB Output is correct
7 Correct 107 ms 106232 KB Output is correct
8 Correct 97 ms 106144 KB Output is correct
9 Correct 111 ms 106232 KB Output is correct
10 Correct 107 ms 106744 KB Output is correct
11 Correct 127 ms 108776 KB Output is correct
12 Correct 104 ms 108024 KB Output is correct
13 Correct 104 ms 108072 KB Output is correct
14 Correct 110 ms 108584 KB Output is correct
15 Correct 110 ms 108536 KB Output is correct
16 Correct 109 ms 108024 KB Output is correct
17 Correct 141 ms 112120 KB Output is correct
18 Correct 164 ms 115704 KB Output is correct
19 Correct 149 ms 115704 KB Output is correct
20 Correct 222 ms 119288 KB Output is correct
21 Correct 118 ms 109564 KB Output is correct
22 Correct 278 ms 115260 KB Output is correct
23 Correct 165 ms 114936 KB Output is correct
24 Correct 192 ms 118008 KB Output is correct
25 Correct 203 ms 118444 KB Output is correct
26 Correct 139 ms 116148 KB Output is correct
27 Correct 140 ms 115976 KB Output is correct
28 Correct 232 ms 119416 KB Output is correct
29 Correct 140 ms 114908 KB Output is correct
30 Correct 132 ms 113912 KB Output is correct
31 Correct 138 ms 114892 KB Output is correct
32 Correct 133 ms 114424 KB Output is correct
33 Correct 159 ms 116928 KB Output is correct
34 Correct 155 ms 116972 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 106044 KB Output is correct
2 Correct 99 ms 106036 KB Output is correct
3 Correct 97 ms 106104 KB Output is correct
4 Correct 110 ms 106084 KB Output is correct
5 Correct 96 ms 106104 KB Output is correct
6 Correct 98 ms 106104 KB Output is correct
7 Correct 110 ms 106128 KB Output is correct
8 Correct 110 ms 106104 KB Output is correct
9 Correct 98 ms 106232 KB Output is correct
10 Correct 113 ms 106788 KB Output is correct
11 Correct 126 ms 108664 KB Output is correct
12 Correct 103 ms 108152 KB Output is correct
13 Correct 116 ms 108152 KB Output is correct
14 Correct 116 ms 108664 KB Output is correct
15 Correct 115 ms 108920 KB Output is correct
16 Correct 109 ms 108024 KB Output is correct
17 Correct 150 ms 112228 KB Output is correct
18 Correct 161 ms 115528 KB Output is correct
19 Correct 150 ms 115628 KB Output is correct
20 Correct 238 ms 119332 KB Output is correct
21 Correct 126 ms 109640 KB Output is correct
22 Correct 161 ms 115268 KB Output is correct
23 Correct 176 ms 114924 KB Output is correct
24 Correct 197 ms 117880 KB Output is correct
25 Correct 231 ms 118396 KB Output is correct
26 Correct 154 ms 116088 KB Output is correct
27 Correct 137 ms 115968 KB Output is correct
28 Correct 246 ms 119416 KB Output is correct
29 Correct 140 ms 114936 KB Output is correct
30 Correct 139 ms 114040 KB Output is correct
31 Correct 134 ms 114924 KB Output is correct
32 Correct 133 ms 114400 KB Output is correct
33 Correct 157 ms 116856 KB Output is correct
34 Correct 165 ms 116856 KB Output is correct
35 Correct 623 ms 151212 KB Output is correct
36 Correct 209 ms 117904 KB Output is correct
37 Correct 562 ms 143224 KB Output is correct
38 Correct 741 ms 160600 KB Output is correct
39 Correct 730 ms 160580 KB Output is correct
40 Correct 815 ms 160992 KB Output is correct
41 Correct 721 ms 160840 KB Output is correct
42 Correct 267 ms 145264 KB Output is correct
43 Correct 270 ms 145104 KB Output is correct
44 Correct 434 ms 148208 KB Output is correct
45 Correct 404 ms 155160 KB Output is correct
46 Correct 394 ms 155128 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 106096 KB Output is correct
2 Correct 110 ms 105976 KB Output is correct
3 Correct 103 ms 106092 KB Output is correct
4 Correct 98 ms 105976 KB Output is correct
5 Correct 97 ms 105976 KB Output is correct
6 Correct 196 ms 106076 KB Output is correct
7 Correct 98 ms 105976 KB Output is correct
8 Correct 98 ms 106156 KB Output is correct
9 Correct 97 ms 106104 KB Output is correct
10 Correct 101 ms 106736 KB Output is correct
11 Correct 109 ms 108664 KB Output is correct
12 Correct 101 ms 108024 KB Output is correct
13 Correct 106 ms 108152 KB Output is correct
14 Correct 109 ms 108820 KB Output is correct
15 Correct 111 ms 108664 KB Output is correct
16 Correct 109 ms 108076 KB Output is correct
17 Correct 150 ms 112160 KB Output is correct
18 Correct 159 ms 115576 KB Output is correct
19 Correct 149 ms 115780 KB Output is correct
20 Correct 213 ms 119160 KB Output is correct
21 Correct 117 ms 109404 KB Output is correct
22 Correct 170 ms 115252 KB Output is correct
23 Correct 163 ms 114936 KB Output is correct
24 Correct 194 ms 117804 KB Output is correct
25 Correct 198 ms 118536 KB Output is correct
26 Correct 138 ms 116088 KB Output is correct
27 Correct 137 ms 115976 KB Output is correct
28 Correct 230 ms 119416 KB Output is correct
29 Correct 140 ms 114936 KB Output is correct
30 Correct 131 ms 113992 KB Output is correct
31 Correct 136 ms 114860 KB Output is correct
32 Correct 135 ms 114424 KB Output is correct
33 Correct 159 ms 116804 KB Output is correct
34 Correct 154 ms 116944 KB Output is correct
35 Correct 568 ms 151416 KB Output is correct
36 Correct 202 ms 117880 KB Output is correct
37 Correct 548 ms 143156 KB Output is correct
38 Correct 795 ms 160836 KB Output is correct
39 Correct 788 ms 160760 KB Output is correct
40 Correct 687 ms 161028 KB Output is correct
41 Correct 705 ms 160888 KB Output is correct
42 Correct 266 ms 145268 KB Output is correct
43 Correct 283 ms 145164 KB Output is correct
44 Correct 400 ms 148308 KB Output is correct
45 Correct 398 ms 155128 KB Output is correct
46 Correct 413 ms 155264 KB Output is correct
47 Execution timed out 1097 ms 200084 KB Time limit exceeded
48 Halted 0 ms 0 KB -