oj.uz

Submission #533081

# Submission time Handle Problem Language Result Execution time Memory
533081 2022-03-04T17:24:31 Z new_acc Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 286 ms 262148 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=3e4+10;
vector<pair<int,int> > graf[1000*1000*3+10];
pair<int,int>w[N];
int l,num[N];
vi li[300];
bitset<N>bb;
bitset<1000*1000*3+10>vis;
vi kol[1000*1000*5+10];
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)5e6;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<=(int)5e6) kol[i+u.se].push_back(u.fi);
		}
	}
	return -1;
}
void solve(){
	cin>>n>>m;
	l=n;
	int p=sqrt(n)/3;
	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 84 ms 188108 KB Output is correct
2 Correct 88 ms 188076 KB Output is correct
3 Correct 91 ms 188260 KB Output is correct
4 Correct 93 ms 188228 KB Output is correct
5 Correct 88 ms 188108 KB Output is correct
6 Correct 86 ms 188128 KB Output is correct
7 Correct 86 ms 188052 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 188144 KB Output is correct
2 Correct 85 ms 188056 KB Output is correct
3 Correct 87 ms 188096 KB Output is correct
4 Correct 94 ms 188100 KB Output is correct
5 Correct 89 ms 188156 KB Output is correct
6 Correct 90 ms 188136 KB Output is correct
7 Correct 87 ms 188100 KB Output is correct
8 Correct 87 ms 188180 KB Output is correct
9 Correct 87 ms 188100 KB Output is correct
10 Correct 87 ms 188216 KB Output is correct
11 Correct 94 ms 188276 KB Output is correct
12 Correct 87 ms 188180 KB Output is correct
13 Correct 90 ms 188164 KB Output is correct
14 Correct 89 ms 188272 KB Output is correct
15 Correct 86 ms 188224 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188160 KB Output is correct
2 Correct 88 ms 188284 KB Output is correct
3 Correct 85 ms 188136 KB Output is correct
4 Correct 94 ms 188080 KB Output is correct
5 Correct 86 ms 188072 KB Output is correct
6 Correct 85 ms 188100 KB Output is correct
7 Correct 91 ms 188184 KB Output is correct
8 Correct 91 ms 188100 KB Output is correct
9 Correct 87 ms 188096 KB Output is correct
10 Correct 88 ms 188204 KB Output is correct
11 Correct 88 ms 188248 KB Output is correct
12 Correct 101 ms 188228 KB Output is correct
13 Correct 90 ms 188224 KB Output is correct
14 Correct 87 ms 188200 KB Output is correct
15 Correct 86 ms 188236 KB Output is correct
16 Correct 95 ms 188228 KB Output is correct
17 Correct 91 ms 188724 KB Output is correct
18 Correct 100 ms 189000 KB Output is correct
19 Correct 97 ms 188612 KB Output is correct
20 Correct 93 ms 188368 KB Output is correct
21 Correct 93 ms 188200 KB Output is correct
22 Correct 94 ms 188512 KB Output is correct
23 Correct 91 ms 188784 KB Output is correct
24 Correct 92 ms 189232 KB Output is correct
25 Correct 88 ms 188540 KB Output is correct
26 Correct 90 ms 189264 KB Output is correct
27 Correct 89 ms 189156 KB Output is correct
28 Correct 92 ms 190232 KB Output is correct
29 Correct 96 ms 189756 KB Output is correct
30 Correct 87 ms 188612 KB Output is correct
31 Correct 85 ms 188812 KB Output is correct
32 Correct 86 ms 188608 KB Output is correct
33 Correct 97 ms 191512 KB Output is correct
34 Correct 93 ms 191428 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 188176 KB Output is correct
2 Correct 86 ms 188132 KB Output is correct
3 Correct 87 ms 188160 KB Output is correct
4 Correct 99 ms 188176 KB Output is correct
5 Correct 86 ms 188080 KB Output is correct
6 Correct 89 ms 188160 KB Output is correct
7 Correct 84 ms 188064 KB Output is correct
8 Correct 89 ms 188132 KB Output is correct
9 Correct 89 ms 188100 KB Output is correct
10 Correct 88 ms 188100 KB Output is correct
11 Correct 87 ms 188320 KB Output is correct
12 Correct 88 ms 188240 KB Output is correct
13 Correct 85 ms 188100 KB Output is correct
14 Correct 88 ms 188292 KB Output is correct
15 Correct 86 ms 188172 KB Output is correct
16 Correct 97 ms 188224 KB Output is correct
17 Correct 89 ms 188760 KB Output is correct
18 Correct 94 ms 188808 KB Output is correct
19 Correct 96 ms 188484 KB Output is correct
20 Correct 91 ms 188372 KB Output is correct
21 Correct 96 ms 188288 KB Output is correct
22 Correct 101 ms 188496 KB Output is correct
23 Correct 89 ms 188844 KB Output is correct
24 Correct 89 ms 189220 KB Output is correct
25 Correct 89 ms 188548 KB Output is correct
26 Correct 92 ms 189252 KB Output is correct
27 Correct 92 ms 189176 KB Output is correct
28 Correct 92 ms 190148 KB Output is correct
29 Correct 92 ms 189676 KB Output is correct
30 Correct 87 ms 188552 KB Output is correct
31 Correct 95 ms 188816 KB Output is correct
32 Correct 89 ms 188632 KB Output is correct
33 Correct 94 ms 191472 KB Output is correct
34 Correct 94 ms 191352 KB Output is correct
35 Correct 97 ms 190404 KB Output is correct
36 Correct 94 ms 189116 KB Output is correct
37 Correct 98 ms 192140 KB Output is correct
38 Correct 100 ms 191816 KB Output is correct
39 Correct 97 ms 191556 KB Output is correct
40 Correct 99 ms 191604 KB Output is correct
41 Correct 110 ms 191972 KB Output is correct
42 Correct 93 ms 189680 KB Output is correct
43 Correct 92 ms 189508 KB Output is correct
44 Correct 90 ms 188740 KB Output is correct
45 Correct 106 ms 196404 KB Output is correct
46 Correct 107 ms 196576 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188188 KB Output is correct
2 Correct 87 ms 188164 KB Output is correct
3 Correct 84 ms 188160 KB Output is correct
4 Correct 92 ms 188176 KB Output is correct
5 Correct 96 ms 188184 KB Output is correct
6 Correct 87 ms 188244 KB Output is correct
7 Correct 85 ms 188132 KB Output is correct
8 Correct 85 ms 188148 KB Output is correct
9 Correct 89 ms 188164 KB Output is correct
10 Correct 85 ms 188124 KB Output is correct
11 Correct 89 ms 188220 KB Output is correct
12 Correct 87 ms 188160 KB Output is correct
13 Correct 85 ms 188100 KB Output is correct
14 Correct 86 ms 188264 KB Output is correct
15 Correct 90 ms 188244 KB Output is correct
16 Correct 98 ms 188244 KB Output is correct
17 Correct 88 ms 188684 KB Output is correct
18 Correct 94 ms 188816 KB Output is correct
19 Correct 94 ms 188484 KB Output is correct
20 Correct 85 ms 188460 KB Output is correct
21 Correct 93 ms 188260 KB Output is correct
22 Correct 97 ms 188652 KB Output is correct
23 Correct 90 ms 188928 KB Output is correct
24 Correct 87 ms 189280 KB Output is correct
25 Correct 86 ms 188544 KB Output is correct
26 Correct 88 ms 189368 KB Output is correct
27 Correct 88 ms 189164 KB Output is correct
28 Correct 102 ms 190208 KB Output is correct
29 Correct 91 ms 189800 KB Output is correct
30 Correct 88 ms 188588 KB Output is correct
31 Correct 86 ms 188740 KB Output is correct
32 Correct 85 ms 188628 KB Output is correct
33 Correct 96 ms 191568 KB Output is correct
34 Correct 94 ms 191428 KB Output is correct
35 Correct 94 ms 190388 KB Output is correct
36 Correct 87 ms 188944 KB Output is correct
37 Correct 100 ms 192088 KB Output is correct
38 Correct 98 ms 191812 KB Output is correct
39 Correct 102 ms 191508 KB Output is correct
40 Correct 111 ms 191556 KB Output is correct
41 Correct 102 ms 191892 KB Output is correct
42 Correct 96 ms 189680 KB Output is correct
43 Correct 98 ms 189436 KB Output is correct
44 Correct 90 ms 188800 KB Output is correct
45 Correct 106 ms 196292 KB Output is correct
46 Correct 108 ms 196396 KB Output is correct
47 Correct 190 ms 223600 KB Output is correct
48 Correct 243 ms 239600 KB Output is correct
49 Correct 167 ms 216880 KB Output is correct
50 Correct 204 ms 229748 KB Output is correct
51 Correct 286 ms 253260 KB Output is correct
52 Runtime error 241 ms 262148 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -