oj.uz

Submission #527443

# Submission time Handle Problem Language Result Execution time Memory
527443 2022-02-17T12:29:48 Z Koosha_mv Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 213920 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=50000,S=100;

int m,n,pos[N],p[N],dist[N][S];
vector<int> vec[N];
set<pair<int,pair<int,int>>> st;

main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m;
	f(i,0,m){
		cin>>pos[i]>>p[i];
		vec[pos[i]].pb(p[i]);
	}
	f(i,0,n) f(j,0,S) dist[i][j]=N;
	dist[pos[0]][0]=0;
	f(i,0,n) f(j,0,S) st.insert({dist[i][j],{i,j}});
	while(st.size()){
		int x=(*st.begin()).S.F,p=(*st.begin()).S.S;
		if(dist[x][p]==N) break;
		//cout<<endl;
		//eror(dist[2][0]);
		//cout<<x<<" "<<p<<" -> "<<dist[x][p]<<endl;
		st.erase(*st.begin());
		if(p>0){
			//eror(x+p);
			//cout<<x+p<<" "<<dist[x][p]+1<<" "<<dist[x+p][0]<<endl;
			if(x+p<n && dist[x][p]+1<dist[x+p][0]){
				//eror(100);
				st.erase({dist[x+p][0],{x+p,0}});
				dist[x+p][0]=dist[x][p]+1;
				st.insert({dist[x+p][0],{x+p,0}});
			}
			if(p<=x && dist[x][p]+1<dist[x-p][0]){
				st.erase({dist[x-p][0],{x-p,0}});
				dist[x-p][0]=dist[x][p]+1;
				st.insert({dist[x-p][0],{x-p,0}});
			}
			
			if(x+p<n && dist[x][p]+1<dist[x+p][p]){
				st.erase({dist[x+p][p],{x+p,p}});
				dist[x+p][p]=dist[x][p]+1;
				st.insert({dist[x+p][p],{x+p,p}});
			}
			if(p<=x && dist[x][p]+1<dist[x-p][p]){
				st.erase({dist[x-p][p],{x-p,p}});
				dist[x-p][p]=dist[x][p]+1;
				st.insert({dist[x-p][p],{x-p,p}});
			}
			continue ;
		}
		for(auto u : vec[x]){
			if(u<S){
				if(dist[x][u]<=dist[x][p]) continue ;
				st.erase({dist[x][u],{x,u}});
				dist[x][u]=dist[x][p];
				st.insert({dist[x][u],{x,u}});
			}
			else{
				for(int i=x%u;i<n;i+=u){
					if(dist[x][p]+abs(x-i)/u<dist[i][p]){
						st.erase({dist[i][p],{i,p}});
						dist[i][p]=dist[x][p]+abs(x-i)/u;
						st.insert({dist[i][p],{i,p}});
					}
				}
			}
		}
	}
	cout<<(dist[pos[1]][0]==N ? -1 : dist[pos[1]][0]);
}

Compilation message

skyscraper.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct
8 Correct 1 ms 1740 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 3 ms 2124 KB Output is correct
11 Correct 5 ms 2252 KB Output is correct
12 Correct 3 ms 2252 KB Output is correct
13 Correct 3 ms 2252 KB Output is correct
14 Correct 6 ms 2252 KB Output is correct
15 Correct 5 ms 2252 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct
8 Correct 2 ms 1740 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 4 ms 2124 KB Output is correct
11 Correct 5 ms 2252 KB Output is correct
12 Correct 3 ms 2252 KB Output is correct
13 Correct 3 ms 2252 KB Output is correct
14 Correct 5 ms 2252 KB Output is correct
15 Correct 5 ms 2252 KB Output is correct
16 Correct 5 ms 2892 KB Output is correct
17 Correct 25 ms 6740 KB Output is correct
18 Correct 44 ms 13800 KB Output is correct
19 Correct 57 ms 15572 KB Output is correct
20 Correct 51 ms 15624 KB Output is correct
21 Correct 9 ms 4300 KB Output is correct
22 Correct 42 ms 14052 KB Output is correct
23 Correct 46 ms 12732 KB Output is correct
24 Correct 56 ms 14908 KB Output is correct
25 Correct 66 ms 15556 KB Output is correct
26 Correct 57 ms 15528 KB Output is correct
27 Correct 57 ms 15716 KB Output is correct
28 Correct 61 ms 15648 KB Output is correct
29 Correct 87 ms 15600 KB Output is correct
30 Correct 76 ms 15580 KB Output is correct
31 Correct 70 ms 15580 KB Output is correct
32 Correct 66 ms 15564 KB Output is correct
33 Correct 121 ms 15640 KB Output is correct
34 Correct 118 ms 15640 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1488 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1488 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1488 KB Output is correct
8 Correct 2 ms 1868 KB Output is correct
9 Correct 2 ms 1872 KB Output is correct
10 Correct 4 ms 2128 KB Output is correct
11 Correct 5 ms 2252 KB Output is correct
12 Correct 3 ms 2144 KB Output is correct
13 Correct 3 ms 2252 KB Output is correct
14 Correct 6 ms 2252 KB Output is correct
15 Correct 5 ms 2252 KB Output is correct
16 Correct 6 ms 2892 KB Output is correct
17 Correct 24 ms 6788 KB Output is correct
18 Correct 44 ms 13824 KB Output is correct
19 Correct 51 ms 15556 KB Output is correct
20 Correct 48 ms 15556 KB Output is correct
21 Correct 9 ms 4300 KB Output is correct
22 Correct 44 ms 14060 KB Output is correct
23 Correct 47 ms 12692 KB Output is correct
24 Correct 61 ms 14944 KB Output is correct
25 Correct 54 ms 15640 KB Output is correct
26 Correct 56 ms 15560 KB Output is correct
27 Correct 53 ms 15548 KB Output is correct
28 Correct 60 ms 15556 KB Output is correct
29 Correct 108 ms 15556 KB Output is correct
30 Correct 63 ms 15476 KB Output is correct
31 Correct 68 ms 15596 KB Output is correct
32 Correct 68 ms 15556 KB Output is correct
33 Correct 122 ms 15632 KB Output is correct
34 Correct 133 ms 15664 KB Output is correct
35 Correct 78 ms 12328 KB Output is correct
36 Correct 34 ms 9308 KB Output is correct
37 Correct 125 ms 15680 KB Output is correct
38 Correct 115 ms 16304 KB Output is correct
39 Correct 160 ms 16420 KB Output is correct
40 Correct 125 ms 16400 KB Output is correct
41 Correct 124 ms 16324 KB Output is correct
42 Correct 61 ms 16196 KB Output is correct
43 Correct 57 ms 16168 KB Output is correct
44 Correct 59 ms 16324 KB Output is correct
45 Correct 144 ms 16284 KB Output is correct
46 Correct 140 ms 16324 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct
8 Correct 3 ms 1740 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 5 ms 2124 KB Output is correct
11 Correct 5 ms 2252 KB Output is correct
12 Correct 3 ms 2192 KB Output is correct
13 Correct 3 ms 2252 KB Output is correct
14 Correct 5 ms 2252 KB Output is correct
15 Correct 5 ms 2252 KB Output is correct
16 Correct 4 ms 2892 KB Output is correct
17 Correct 24 ms 6724 KB Output is correct
18 Correct 43 ms 13764 KB Output is correct
19 Correct 51 ms 15484 KB Output is correct
20 Correct 50 ms 15564 KB Output is correct
21 Correct 11 ms 4196 KB Output is correct
22 Correct 42 ms 14020 KB Output is correct
23 Correct 46 ms 12736 KB Output is correct
24 Correct 55 ms 14932 KB Output is correct
25 Correct 53 ms 15628 KB Output is correct
26 Correct 57 ms 15604 KB Output is correct
27 Correct 69 ms 15624 KB Output is correct
28 Correct 68 ms 15668 KB Output is correct
29 Correct 90 ms 15572 KB Output is correct
30 Correct 62 ms 15480 KB Output is correct
31 Correct 77 ms 15552 KB Output is correct
32 Correct 68 ms 15480 KB Output is correct
33 Correct 113 ms 15640 KB Output is correct
34 Correct 114 ms 15716 KB Output is correct
35 Correct 73 ms 12316 KB Output is correct
36 Correct 34 ms 9292 KB Output is correct
37 Correct 126 ms 15692 KB Output is correct
38 Correct 119 ms 16388 KB Output is correct
39 Correct 131 ms 16420 KB Output is correct
40 Correct 123 ms 16424 KB Output is correct
41 Correct 120 ms 16416 KB Output is correct
42 Correct 61 ms 16176 KB Output is correct
43 Correct 58 ms 16264 KB Output is correct
44 Correct 67 ms 16308 KB Output is correct
45 Correct 142 ms 16348 KB Output is correct
46 Correct 148 ms 16324 KB Output is correct
47 Correct 918 ms 89260 KB Output is correct
48 Correct 673 ms 165924 KB Output is correct
49 Correct 756 ms 181016 KB Output is correct
50 Correct 879 ms 198720 KB Output is correct
51 Execution timed out 1099 ms 213920 KB Time limit exceeded
52 Halted 0 ms 0 KB -