oj.uz

Submission #533084

# Submission time Handle Problem Language Result Execution time Memory
533084 2022-03-04T17:28:54 Z new_acc Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 267 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)/7;
	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 75 ms 164676 KB Output is correct
2 Correct 75 ms 164696 KB Output is correct
3 Correct 75 ms 164668 KB Output is correct
4 Correct 82 ms 164688 KB Output is correct
5 Correct 75 ms 164704 KB Output is correct
6 Correct 73 ms 164676 KB Output is correct
7 Correct 75 ms 164632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 164696 KB Output is correct
2 Correct 76 ms 164644 KB Output is correct
3 Correct 76 ms 164652 KB Output is correct
4 Correct 85 ms 164604 KB Output is correct
5 Correct 74 ms 164676 KB Output is correct
6 Correct 73 ms 164656 KB Output is correct
7 Correct 75 ms 164676 KB Output is correct
8 Correct 74 ms 164696 KB Output is correct
9 Correct 79 ms 164804 KB Output is correct
10 Correct 77 ms 164656 KB Output is correct
11 Correct 78 ms 164768 KB Output is correct
12 Correct 75 ms 164740 KB Output is correct
13 Correct 76 ms 164644 KB Output is correct
14 Correct 78 ms 164764 KB Output is correct
15 Correct 80 ms 164820 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 164696 KB Output is correct
2 Correct 76 ms 164588 KB Output is correct
3 Correct 76 ms 164676 KB Output is correct
4 Correct 86 ms 164700 KB Output is correct
5 Correct 79 ms 164676 KB Output is correct
6 Correct 82 ms 164660 KB Output is correct
7 Correct 75 ms 164696 KB Output is correct
8 Correct 81 ms 164688 KB Output is correct
9 Correct 78 ms 164644 KB Output is correct
10 Correct 76 ms 164668 KB Output is correct
11 Correct 78 ms 164860 KB Output is correct
12 Correct 74 ms 164676 KB Output is correct
13 Correct 77 ms 164748 KB Output is correct
14 Correct 76 ms 164780 KB Output is correct
15 Correct 76 ms 164680 KB Output is correct
16 Correct 82 ms 164884 KB Output is correct
17 Correct 82 ms 165140 KB Output is correct
18 Correct 83 ms 164828 KB Output is correct
19 Correct 82 ms 164936 KB Output is correct
20 Correct 74 ms 164944 KB Output is correct
21 Correct 82 ms 164664 KB Output is correct
22 Correct 82 ms 164924 KB Output is correct
23 Correct 79 ms 165060 KB Output is correct
24 Correct 76 ms 165212 KB Output is correct
25 Correct 75 ms 165052 KB Output is correct
26 Correct 75 ms 165316 KB Output is correct
27 Correct 77 ms 165272 KB Output is correct
28 Correct 81 ms 165828 KB Output is correct
29 Correct 82 ms 165700 KB Output is correct
30 Correct 76 ms 165136 KB Output is correct
31 Correct 80 ms 165344 KB Output is correct
32 Correct 75 ms 165076 KB Output is correct
33 Correct 80 ms 167152 KB Output is correct
34 Correct 82 ms 167112 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 164604 KB Output is correct
2 Correct 74 ms 164676 KB Output is correct
3 Correct 78 ms 164676 KB Output is correct
4 Correct 82 ms 164688 KB Output is correct
5 Correct 76 ms 164660 KB Output is correct
6 Correct 77 ms 164632 KB Output is correct
7 Correct 75 ms 164628 KB Output is correct
8 Correct 78 ms 164596 KB Output is correct
9 Correct 76 ms 164596 KB Output is correct
10 Correct 80 ms 164616 KB Output is correct
11 Correct 76 ms 164768 KB Output is correct
12 Correct 80 ms 164932 KB Output is correct
13 Correct 76 ms 164724 KB Output is correct
14 Correct 76 ms 164676 KB Output is correct
15 Correct 83 ms 164780 KB Output is correct
16 Correct 82 ms 164736 KB Output is correct
17 Correct 80 ms 165020 KB Output is correct
18 Correct 84 ms 164900 KB Output is correct
19 Correct 82 ms 165004 KB Output is correct
20 Correct 75 ms 164968 KB Output is correct
21 Correct 82 ms 164724 KB Output is correct
22 Correct 84 ms 164972 KB Output is correct
23 Correct 78 ms 164984 KB Output is correct
24 Correct 77 ms 165184 KB Output is correct
25 Correct 78 ms 165136 KB Output is correct
26 Correct 78 ms 165312 KB Output is correct
27 Correct 77 ms 165312 KB Output is correct
28 Correct 79 ms 165708 KB Output is correct
29 Correct 78 ms 165736 KB Output is correct
30 Correct 78 ms 165064 KB Output is correct
31 Correct 79 ms 165316 KB Output is correct
32 Correct 75 ms 165060 KB Output is correct
33 Correct 85 ms 167188 KB Output is correct
34 Correct 82 ms 167008 KB Output is correct
35 Correct 83 ms 166540 KB Output is correct
36 Correct 76 ms 165100 KB Output is correct
37 Correct 83 ms 168004 KB Output is correct
38 Correct 87 ms 167720 KB Output is correct
39 Correct 87 ms 167348 KB Output is correct
40 Correct 86 ms 167396 KB Output is correct
41 Correct 85 ms 167624 KB Output is correct
42 Correct 80 ms 165612 KB Output is correct
43 Correct 79 ms 165572 KB Output is correct
44 Correct 83 ms 165240 KB Output is correct
45 Correct 97 ms 172100 KB Output is correct
46 Correct 91 ms 171888 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164676 KB Output is correct
2 Correct 75 ms 164676 KB Output is correct
3 Correct 77 ms 164696 KB Output is correct
4 Correct 85 ms 164740 KB Output is correct
5 Correct 79 ms 164820 KB Output is correct
6 Correct 74 ms 164652 KB Output is correct
7 Correct 74 ms 164648 KB Output is correct
8 Correct 75 ms 164676 KB Output is correct
9 Correct 75 ms 164664 KB Output is correct
10 Correct 80 ms 164844 KB Output is correct
11 Correct 76 ms 164800 KB Output is correct
12 Correct 77 ms 164696 KB Output is correct
13 Correct 75 ms 164676 KB Output is correct
14 Correct 74 ms 164804 KB Output is correct
15 Correct 76 ms 164860 KB Output is correct
16 Correct 87 ms 164676 KB Output is correct
17 Correct 76 ms 164932 KB Output is correct
18 Correct 82 ms 164776 KB Output is correct
19 Correct 84 ms 164968 KB Output is correct
20 Correct 78 ms 164936 KB Output is correct
21 Correct 86 ms 164868 KB Output is correct
22 Correct 83 ms 164892 KB Output is correct
23 Correct 79 ms 164876 KB Output is correct
24 Correct 77 ms 165232 KB Output is correct
25 Correct 101 ms 165164 KB Output is correct
26 Correct 80 ms 165316 KB Output is correct
27 Correct 77 ms 165344 KB Output is correct
28 Correct 81 ms 165772 KB Output is correct
29 Correct 77 ms 165808 KB Output is correct
30 Correct 76 ms 165024 KB Output is correct
31 Correct 79 ms 165328 KB Output is correct
32 Correct 79 ms 165188 KB Output is correct
33 Correct 80 ms 167108 KB Output is correct
34 Correct 82 ms 167108 KB Output is correct
35 Correct 85 ms 166528 KB Output is correct
36 Correct 78 ms 165012 KB Output is correct
37 Correct 92 ms 168036 KB Output is correct
38 Correct 96 ms 167748 KB Output is correct
39 Correct 87 ms 167368 KB Output is correct
40 Correct 88 ms 167396 KB Output is correct
41 Correct 89 ms 167640 KB Output is correct
42 Correct 86 ms 165684 KB Output is correct
43 Correct 85 ms 165572 KB Output is correct
44 Correct 80 ms 165220 KB Output is correct
45 Correct 94 ms 172072 KB Output is correct
46 Correct 92 ms 171876 KB Output is correct
47 Correct 129 ms 184440 KB Output is correct
48 Correct 158 ms 191172 KB Output is correct
49 Correct 121 ms 177348 KB Output is correct
50 Correct 137 ms 185244 KB Output is correct
51 Correct 166 ms 199584 KB Output is correct
52 Correct 182 ms 201676 KB Output is correct
53 Correct 96 ms 170840 KB Output is correct
54 Correct 90 ms 167108 KB Output is correct
55 Correct 102 ms 171160 KB Output is correct
56 Correct 93 ms 168876 KB Output is correct
57 Correct 144 ms 190556 KB Output is correct
58 Correct 117 ms 178216 KB Output is correct
59 Correct 156 ms 191528 KB Output is correct
60 Correct 161 ms 192160 KB Output is correct
61 Correct 148 ms 185744 KB Output is correct
62 Correct 182 ms 208964 KB Output is correct
63 Correct 129 ms 193808 KB Output is correct
64 Correct 144 ms 200392 KB Output is correct
65 Correct 175 ms 216352 KB Output is correct
66 Runtime error 267 ms 262148 KB Execution killed with signal 9
67 Halted 0 ms 0 KB -