oj.uz

Submission #533067

# Submission time Handle Problem Language Result Execution time Memory
533067 2022-03-04T16:54:55 Z new_acc Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 21 ms 35708 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=5e5+10;
vector<pair<int,int> > graf[N];
pair<int,int>w[N];
int l,num[N];
vi li[300];
bitset<N>bb;
bitset<N>vis;
vi kol[N*2];
int n,m;
void single(int x){
	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>=0;i++){
		if(kol[i].empty()) break;
		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]) 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 17 ms 35512 KB Output is correct
2 Correct 17 ms 35464 KB Output is correct
3 Correct 18 ms 35532 KB Output is correct
4 Correct 19 ms 35500 KB Output is correct
5 Correct 17 ms 35556 KB Output is correct
6 Correct 17 ms 35568 KB Output is correct
7 Correct 16 ms 35524 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35532 KB Output is correct
2 Correct 16 ms 35488 KB Output is correct
3 Correct 18 ms 35532 KB Output is correct
4 Correct 17 ms 35532 KB Output is correct
5 Correct 17 ms 35532 KB Output is correct
6 Correct 20 ms 35548 KB Output is correct
7 Correct 17 ms 35520 KB Output is correct
8 Correct 18 ms 35532 KB Output is correct
9 Correct 17 ms 35520 KB Output is correct
10 Correct 17 ms 35636 KB Output is correct
11 Correct 18 ms 35592 KB Output is correct
12 Incorrect 18 ms 35660 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35532 KB Output is correct
2 Correct 16 ms 35552 KB Output is correct
3 Correct 17 ms 35560 KB Output is correct
4 Correct 18 ms 35532 KB Output is correct
5 Correct 17 ms 35564 KB Output is correct
6 Correct 18 ms 35536 KB Output is correct
7 Correct 18 ms 35560 KB Output is correct
8 Correct 17 ms 35508 KB Output is correct
9 Correct 20 ms 35652 KB Output is correct
10 Correct 19 ms 35532 KB Output is correct
11 Correct 18 ms 35624 KB Output is correct
12 Incorrect 19 ms 35572 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35504 KB Output is correct
2 Correct 16 ms 35560 KB Output is correct
3 Correct 17 ms 35552 KB Output is correct
4 Correct 17 ms 35532 KB Output is correct
5 Correct 17 ms 35556 KB Output is correct
6 Correct 17 ms 35548 KB Output is correct
7 Correct 21 ms 35524 KB Output is correct
8 Correct 18 ms 35532 KB Output is correct
9 Correct 17 ms 35480 KB Output is correct
10 Correct 20 ms 35540 KB Output is correct
11 Correct 19 ms 35612 KB Output is correct
12 Incorrect 17 ms 35644 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35484 KB Output is correct
2 Correct 16 ms 35532 KB Output is correct
3 Correct 17 ms 35556 KB Output is correct
4 Correct 16 ms 35480 KB Output is correct
5 Correct 17 ms 35556 KB Output is correct
6 Correct 17 ms 35556 KB Output is correct
7 Correct 19 ms 35508 KB Output is correct
8 Correct 18 ms 35576 KB Output is correct
9 Correct 17 ms 35492 KB Output is correct
10 Correct 17 ms 35532 KB Output is correct
11 Correct 18 ms 35708 KB Output is correct
12 Incorrect 18 ms 35568 KB Output isn't correct
13 Halted 0 ms 0 KB -