oj.uz

Submission #533082

# Submission time Handle Problem Language Result Execution time Memory
533082 2022-03-04T17:25:36 Z new_acc Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 259 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*2+10];
pair<int,int>w[N];
int l,num[N];
vi li[300];
bitset<N>bb;
bitset<1000*1000*2+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)/4;
	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 80 ms 164632 KB Output is correct
2 Correct 79 ms 164668 KB Output is correct
3 Correct 74 ms 164616 KB Output is correct
4 Correct 85 ms 164608 KB Output is correct
5 Correct 74 ms 164692 KB Output is correct
6 Correct 74 ms 164700 KB Output is correct
7 Correct 78 ms 164696 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 164644 KB Output is correct
2 Correct 75 ms 164584 KB Output is correct
3 Correct 77 ms 164652 KB Output is correct
4 Correct 83 ms 164640 KB Output is correct
5 Correct 77 ms 164620 KB Output is correct
6 Correct 81 ms 164676 KB Output is correct
7 Correct 78 ms 164620 KB Output is correct
8 Correct 77 ms 164692 KB Output is correct
9 Correct 75 ms 164676 KB Output is correct
10 Correct 76 ms 164676 KB Output is correct
11 Correct 78 ms 164680 KB Output is correct
12 Correct 84 ms 164728 KB Output is correct
13 Correct 82 ms 164640 KB Output is correct
14 Correct 75 ms 164704 KB Output is correct
15 Correct 77 ms 164800 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 164608 KB Output is correct
2 Correct 77 ms 164676 KB Output is correct
3 Correct 74 ms 164676 KB Output is correct
4 Correct 83 ms 164588 KB Output is correct
5 Correct 76 ms 164652 KB Output is correct
6 Correct 76 ms 164600 KB Output is correct
7 Correct 76 ms 164632 KB Output is correct
8 Correct 77 ms 164732 KB Output is correct
9 Correct 74 ms 164712 KB Output is correct
10 Correct 76 ms 164628 KB Output is correct
11 Correct 78 ms 164796 KB Output is correct
12 Correct 76 ms 164740 KB Output is correct
13 Correct 77 ms 164704 KB Output is correct
14 Correct 79 ms 164692 KB Output is correct
15 Correct 77 ms 164800 KB Output is correct
16 Correct 85 ms 164700 KB Output is correct
17 Correct 77 ms 165068 KB Output is correct
18 Correct 95 ms 165220 KB Output is correct
19 Correct 88 ms 164988 KB Output is correct
20 Correct 78 ms 164884 KB Output is correct
21 Correct 85 ms 164772 KB Output is correct
22 Correct 97 ms 164872 KB Output is correct
23 Correct 76 ms 164988 KB Output is correct
24 Correct 78 ms 165528 KB Output is correct
25 Correct 80 ms 165068 KB Output is correct
26 Correct 79 ms 165732 KB Output is correct
27 Correct 77 ms 165524 KB Output is correct
28 Correct 80 ms 166280 KB Output is correct
29 Correct 79 ms 166036 KB Output is correct
30 Correct 83 ms 165292 KB Output is correct
31 Correct 77 ms 165316 KB Output is correct
32 Correct 77 ms 165156 KB Output is correct
33 Correct 87 ms 167616 KB Output is correct
34 Correct 83 ms 167640 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164688 KB Output is correct
2 Correct 90 ms 164640 KB Output is correct
3 Correct 75 ms 164676 KB Output is correct
4 Correct 90 ms 164696 KB Output is correct
5 Correct 87 ms 164688 KB Output is correct
6 Correct 76 ms 164680 KB Output is correct
7 Correct 78 ms 164804 KB Output is correct
8 Correct 76 ms 164612 KB Output is correct
9 Correct 75 ms 164676 KB Output is correct
10 Correct 77 ms 164620 KB Output is correct
11 Correct 77 ms 164804 KB Output is correct
12 Correct 80 ms 164716 KB Output is correct
13 Correct 77 ms 164736 KB Output is correct
14 Correct 78 ms 164804 KB Output is correct
15 Correct 77 ms 164700 KB Output is correct
16 Correct 84 ms 164700 KB Output is correct
17 Correct 75 ms 165148 KB Output is correct
18 Correct 90 ms 165228 KB Output is correct
19 Correct 86 ms 164980 KB Output is correct
20 Correct 77 ms 164960 KB Output is correct
21 Correct 84 ms 164700 KB Output is correct
22 Correct 83 ms 164912 KB Output is correct
23 Correct 78 ms 165048 KB Output is correct
24 Correct 81 ms 165580 KB Output is correct
25 Correct 80 ms 165116 KB Output is correct
26 Correct 78 ms 165700 KB Output is correct
27 Correct 79 ms 165552 KB Output is correct
28 Correct 82 ms 166336 KB Output is correct
29 Correct 80 ms 166028 KB Output is correct
30 Correct 77 ms 165116 KB Output is correct
31 Correct 78 ms 165260 KB Output is correct
32 Correct 76 ms 165060 KB Output is correct
33 Correct 83 ms 167668 KB Output is correct
34 Correct 80 ms 167648 KB Output is correct
35 Correct 86 ms 166712 KB Output is correct
36 Correct 80 ms 165248 KB Output is correct
37 Correct 85 ms 168352 KB Output is correct
38 Correct 88 ms 168132 KB Output is correct
39 Correct 88 ms 167748 KB Output is correct
40 Correct 102 ms 167724 KB Output is correct
41 Correct 91 ms 168124 KB Output is correct
42 Correct 81 ms 166096 KB Output is correct
43 Correct 88 ms 165856 KB Output is correct
44 Correct 80 ms 165236 KB Output is correct
45 Correct 93 ms 172504 KB Output is correct
46 Correct 96 ms 172436 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 164672 KB Output is correct
2 Correct 76 ms 164588 KB Output is correct
3 Correct 81 ms 164576 KB Output is correct
4 Correct 83 ms 164700 KB Output is correct
5 Correct 77 ms 164804 KB Output is correct
6 Correct 77 ms 164592 KB Output is correct
7 Correct 74 ms 164684 KB Output is correct
8 Correct 75 ms 164588 KB Output is correct
9 Correct 79 ms 164676 KB Output is correct
10 Correct 75 ms 164740 KB Output is correct
11 Correct 78 ms 164796 KB Output is correct
12 Correct 78 ms 164644 KB Output is correct
13 Correct 75 ms 164748 KB Output is correct
14 Correct 78 ms 164804 KB Output is correct
15 Correct 76 ms 164784 KB Output is correct
16 Correct 83 ms 164692 KB Output is correct
17 Correct 78 ms 165072 KB Output is correct
18 Correct 86 ms 165212 KB Output is correct
19 Correct 85 ms 164932 KB Output is correct
20 Correct 78 ms 164928 KB Output is correct
21 Correct 83 ms 164728 KB Output is correct
22 Correct 84 ms 164876 KB Output is correct
23 Correct 80 ms 165064 KB Output is correct
24 Correct 80 ms 165572 KB Output is correct
25 Correct 79 ms 165140 KB Output is correct
26 Correct 78 ms 165700 KB Output is correct
27 Correct 80 ms 165572 KB Output is correct
28 Correct 80 ms 166296 KB Output is correct
29 Correct 79 ms 166208 KB Output is correct
30 Correct 83 ms 165060 KB Output is correct
31 Correct 77 ms 165244 KB Output is correct
32 Correct 75 ms 165100 KB Output is correct
33 Correct 83 ms 167620 KB Output is correct
34 Correct 81 ms 167580 KB Output is correct
35 Correct 85 ms 166764 KB Output is correct
36 Correct 81 ms 165356 KB Output is correct
37 Correct 87 ms 168304 KB Output is correct
38 Correct 88 ms 168072 KB Output is correct
39 Correct 86 ms 167848 KB Output is correct
40 Correct 91 ms 167756 KB Output is correct
41 Correct 91 ms 168064 KB Output is correct
42 Correct 81 ms 166084 KB Output is correct
43 Correct 81 ms 165796 KB Output is correct
44 Correct 79 ms 165316 KB Output is correct
45 Correct 95 ms 172548 KB Output is correct
46 Correct 97 ms 172452 KB Output is correct
47 Correct 152 ms 192864 KB Output is correct
48 Correct 186 ms 205684 KB Output is correct
49 Correct 139 ms 186848 KB Output is correct
50 Correct 179 ms 201096 KB Output is correct
51 Correct 204 ms 214528 KB Output is correct
52 Correct 217 ms 220708 KB Output is correct
53 Correct 94 ms 171212 KB Output is correct
54 Correct 95 ms 167108 KB Output is correct
55 Correct 97 ms 171148 KB Output is correct
56 Correct 105 ms 169072 KB Output is correct
57 Correct 150 ms 191812 KB Output is correct
58 Correct 135 ms 183968 KB Output is correct
59 Correct 217 ms 210656 KB Output is correct
60 Correct 215 ms 211140 KB Output is correct
61 Correct 173 ms 195496 KB Output is correct
62 Correct 235 ms 228832 KB Output is correct
63 Correct 128 ms 194076 KB Output is correct
64 Correct 139 ms 200548 KB Output is correct
65 Correct 176 ms 216640 KB Output is correct
66 Runtime error 259 ms 262148 KB Execution killed with signal 9
67 Halted 0 ms 0 KB -