oj.uz

Submission #533071

# Submission time Handle Problem Language Result Execution time Memory
533071 2022-03-04T17:06:22 Z new_acc Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 429 ms 262144 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
vector<pair<int,int> > graf[N*3];
pair<int,int>w[N];
int l,num[N];
vi li[300];
bitset<N>bb;
bitset<N>vis;
vi kol[N];
int n,m;
void single(int x){
	if(li[x].empty()) return;
	for(int i=1;i<=x;i++){
		num[i]=++l;
		graf[l].push_back({i,0});
	}
	for(int i=x+1;i<=n;i++){
		num[i]=++l;
		graf[l].push_back({i,0}),graf[l].push_back({num[i-x],1});
	}
	for(int i=1;i<=n;i++) bb[i]=0;
	for(auto u:li[x]) bb[w[u].fi]=1;
	for(int i=1;i<=n;i++) if(bb[i]) graf[i].push_back({num[i],0});
	for(int i=n;i>=n-x+1;i--){
		num[i]=++l;
		graf[l].push_back({i,0});
	}
	for(int i=n-x;i>=1;i--){
		num[i]=++l;
		graf[l].push_back({i,0}),graf[l].push_back({num[i+x],1});
	}
	for(int i=1;i<=n;i++) if(bb[i]) graf[i].push_back({num[i],0});
}
int Dijkstra(int p,int k){
	kol[0].push_back(p);
	for(int i=0;i<=(int)1e6;i++){
		for(int j=0;j<kol[i].size();j++){
			int v=kol[i][j];
			if(vis[v]) continue;
			vis[v]=1;
			if(v==k) return i;
			for(auto u:graf[v])
				if(!vis[u.fi] and i+u.se<N) kol[i+u.se].push_back(u.fi);
		}
	}
	return -1;
}
void solve(){
	cin>>n>>m;
	l=n;
	int p=sqrt(n);
	if(p*p!=n) p++;
	for(int i=1;i<=m;i++){
		cin>>w[i].fi>>w[i].se;
		w[i].fi++;
		if(w[i].se>p){
			for(int j=w[i].fi+w[i].se;j<=n;j+=w[i].se) graf[w[i].fi].push_back({j,(j-w[i].fi)/w[i].se});
			for(int j=w[i].fi-w[i].se;j>=1;j-=w[i].se) graf[w[i].fi].push_back({j,(w[i].fi-j)/w[i].se});
		}else li[w[i].se].push_back(i);
	}
	for(int i=1;i<=p;i++) single(i);		
	cout<<Dijkstra(w[1].fi,w[2].fi)<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message

skyscraper.cpp: In function 'int Dijkstra(int, int)':
skyscraper.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int j=0;j<kol[i].size();j++){
      |               ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94152 KB Output is correct
2 Correct 47 ms 94260 KB Output is correct
3 Correct 52 ms 94244 KB Output is correct
4 Correct 45 ms 94244 KB Output is correct
5 Correct 43 ms 94148 KB Output is correct
6 Correct 43 ms 94196 KB Output is correct
7 Correct 44 ms 94148 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94268 KB Output is correct
2 Correct 52 ms 94208 KB Output is correct
3 Correct 44 ms 94204 KB Output is correct
4 Correct 47 ms 94244 KB Output is correct
5 Correct 44 ms 94228 KB Output is correct
6 Correct 45 ms 94252 KB Output is correct
7 Correct 45 ms 94164 KB Output is correct
8 Correct 45 ms 94148 KB Output is correct
9 Correct 45 ms 94184 KB Output is correct
10 Correct 47 ms 94404 KB Output is correct
11 Correct 50 ms 94296 KB Output is correct
12 Correct 57 ms 94248 KB Output is correct
13 Correct 48 ms 94304 KB Output is correct
14 Correct 45 ms 94376 KB Output is correct
15 Correct 45 ms 94376 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94156 KB Output is correct
2 Correct 50 ms 94284 KB Output is correct
3 Correct 50 ms 94252 KB Output is correct
4 Correct 47 ms 94252 KB Output is correct
5 Correct 42 ms 94156 KB Output is correct
6 Correct 44 ms 94156 KB Output is correct
7 Correct 46 ms 94216 KB Output is correct
8 Correct 45 ms 94160 KB Output is correct
9 Correct 45 ms 94208 KB Output is correct
10 Correct 46 ms 94452 KB Output is correct
11 Correct 57 ms 94272 KB Output is correct
12 Correct 44 ms 94252 KB Output is correct
13 Correct 43 ms 94248 KB Output is correct
14 Correct 47 ms 94316 KB Output is correct
15 Correct 44 ms 94416 KB Output is correct
16 Correct 48 ms 94436 KB Output is correct
17 Correct 57 ms 95764 KB Output is correct
18 Correct 52 ms 96288 KB Output is correct
19 Correct 52 ms 95428 KB Output is correct
20 Correct 51 ms 94496 KB Output is correct
21 Correct 52 ms 94472 KB Output is correct
22 Correct 56 ms 95604 KB Output is correct
23 Correct 49 ms 96068 KB Output is correct
24 Correct 60 ms 98008 KB Output is correct
25 Correct 45 ms 94660 KB Output is correct
26 Correct 52 ms 97324 KB Output is correct
27 Correct 51 ms 96308 KB Output is correct
28 Correct 56 ms 98576 KB Output is correct
29 Correct 59 ms 98620 KB Output is correct
30 Correct 47 ms 95496 KB Output is correct
31 Correct 50 ms 96656 KB Output is correct
32 Correct 52 ms 95312 KB Output is correct
33 Correct 71 ms 100984 KB Output is correct
34 Correct 79 ms 100636 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94148 KB Output is correct
2 Correct 45 ms 94168 KB Output is correct
3 Correct 44 ms 94256 KB Output is correct
4 Correct 48 ms 94156 KB Output is correct
5 Correct 45 ms 94148 KB Output is correct
6 Correct 44 ms 94148 KB Output is correct
7 Correct 49 ms 94228 KB Output is correct
8 Correct 44 ms 94144 KB Output is correct
9 Correct 42 ms 94224 KB Output is correct
10 Correct 48 ms 94248 KB Output is correct
11 Correct 59 ms 94268 KB Output is correct
12 Correct 52 ms 94308 KB Output is correct
13 Correct 43 ms 94312 KB Output is correct
14 Correct 45 ms 94344 KB Output is correct
15 Correct 45 ms 94376 KB Output is correct
16 Correct 48 ms 94412 KB Output is correct
17 Correct 59 ms 95540 KB Output is correct
18 Correct 51 ms 96352 KB Output is correct
19 Correct 49 ms 95664 KB Output is correct
20 Correct 44 ms 94560 KB Output is correct
21 Correct 45 ms 94384 KB Output is correct
22 Correct 50 ms 95608 KB Output is correct
23 Correct 49 ms 96048 KB Output is correct
24 Correct 57 ms 97768 KB Output is correct
25 Correct 45 ms 94652 KB Output is correct
26 Correct 54 ms 97436 KB Output is correct
27 Correct 51 ms 96408 KB Output is correct
28 Correct 59 ms 98628 KB Output is correct
29 Correct 57 ms 98648 KB Output is correct
30 Correct 48 ms 95428 KB Output is correct
31 Correct 50 ms 96588 KB Output is correct
32 Correct 46 ms 95424 KB Output is correct
33 Correct 63 ms 100908 KB Output is correct
34 Correct 71 ms 100624 KB Output is correct
35 Correct 64 ms 98676 KB Output is correct
36 Correct 49 ms 96460 KB Output is correct
37 Correct 66 ms 101528 KB Output is correct
38 Correct 67 ms 101444 KB Output is correct
39 Correct 68 ms 101232 KB Output is correct
40 Correct 73 ms 101292 KB Output is correct
41 Correct 71 ms 101504 KB Output is correct
42 Correct 57 ms 97868 KB Output is correct
43 Correct 67 ms 96636 KB Output is correct
44 Correct 51 ms 94884 KB Output is correct
45 Correct 90 ms 105924 KB Output is correct
46 Correct 77 ms 105796 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94224 KB Output is correct
2 Correct 46 ms 94200 KB Output is correct
3 Correct 46 ms 94228 KB Output is correct
4 Correct 45 ms 94148 KB Output is correct
5 Correct 47 ms 94252 KB Output is correct
6 Correct 55 ms 94252 KB Output is correct
7 Correct 44 ms 94236 KB Output is correct
8 Correct 48 ms 94196 KB Output is correct
9 Correct 47 ms 94268 KB Output is correct
10 Correct 54 ms 94208 KB Output is correct
11 Correct 46 ms 94284 KB Output is correct
12 Correct 43 ms 94252 KB Output is correct
13 Correct 44 ms 94204 KB Output is correct
14 Correct 44 ms 94412 KB Output is correct
15 Correct 46 ms 94448 KB Output is correct
16 Correct 52 ms 94532 KB Output is correct
17 Correct 47 ms 95584 KB Output is correct
18 Correct 52 ms 96336 KB Output is correct
19 Correct 49 ms 95520 KB Output is correct
20 Correct 44 ms 94504 KB Output is correct
21 Correct 45 ms 94444 KB Output is correct
22 Correct 50 ms 95564 KB Output is correct
23 Correct 53 ms 96132 KB Output is correct
24 Correct 59 ms 97856 KB Output is correct
25 Correct 47 ms 94644 KB Output is correct
26 Correct 49 ms 97444 KB Output is correct
27 Correct 50 ms 96248 KB Output is correct
28 Correct 70 ms 98660 KB Output is correct
29 Correct 58 ms 98592 KB Output is correct
30 Correct 48 ms 95428 KB Output is correct
31 Correct 56 ms 96576 KB Output is correct
32 Correct 49 ms 95424 KB Output is correct
33 Correct 78 ms 100964 KB Output is correct
34 Correct 65 ms 100668 KB Output is correct
35 Correct 59 ms 98760 KB Output is correct
36 Correct 51 ms 96392 KB Output is correct
37 Correct 66 ms 101516 KB Output is correct
38 Correct 83 ms 101548 KB Output is correct
39 Correct 67 ms 101168 KB Output is correct
40 Correct 67 ms 101316 KB Output is correct
41 Correct 67 ms 101528 KB Output is correct
42 Correct 57 ms 97872 KB Output is correct
43 Correct 61 ms 96708 KB Output is correct
44 Correct 50 ms 94948 KB Output is correct
45 Correct 78 ms 105864 KB Output is correct
46 Correct 72 ms 105740 KB Output is correct
47 Correct 306 ms 186140 KB Output is correct
48 Runtime error 429 ms 262144 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -