oj.uz

Submission #762318

# Submission time Handle Problem Language Result Execution time Memory
762318 2023-06-21T10:11:05 Z aihay Sky Walking (IOI19_walk) C++14
24 / 100
 4000 ms 818168 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define F first
#define S second
#define PB push_back
#define FR(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,n) FR(i,0,n)
#define SZ(x) int(x.size())
const LL MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,m,s,g,x[100010],h[100010],l[100010],r[100010],y[100010],idxx;
pair<int,int> srtb[100010];
pair<int,pair<int,int>> srts[100010];
LL cst[1000010];
vector<int> v[5000010];
map<pair<int,int>,int> mp;
pair<int,int> inter[5000010];
LL dijk(){
	for(int i=0;i<idxx;i++)
		cst[i]=MAAX;
	priority_queue<pair<LL,int>> pq;
	pq.push({0,1});
	while(pq.size()){
		LL cost=-pq.top().F;
		int idx=pq.top().S;
		pq.pop();
		if(cost>cst[idx])
			continue;
		cst[idx]=cost;
		if(idx==2)
			break;
		for(int i=0;i<v[idx].size();i++){
			int x1=inter[idx].F,x2=inter[v[idx][i]].F;
			int y1=inter[idx].S,y2=inter[v[idx][i]].S;
			LL ncst=cost+abs(x2-x1)+abs(y2-y1);
			int nidx=v[idx][i];
			if(ncst<cst[nidx]){
				cst[nidx]=ncst;
				pq.push({-ncst,nidx});
			}
		}
	}
	if(cst[2]==MAAX)
		cst[2]=-1;
	return cst[2];
}
map<int,vector<int>> vec;
LL min_distance(vector<int> X,vector<int> H,vector<int> L,vector<int> R,vector<int> Y,int S,int G){
	n=X.size();
	m=L.size();
	s=S,g=G;
	for(int i=0;i<n;i++){
		x[i]=X[i];
		h[i]=H[i];
		vec[x[i]].PB(0);
		srtb[i]={-h[i],x[i]};
	}
	sort(srtb,srtb+n);
	idxx++;
	mp[{x[s],0}]=idxx++;
	inter[1]={x[s],0};
	mp[{x[g],0}]=idxx++;
	inter[2]={x[g],0};
	for(int i=0;i<n;i++){
		srtb[i].F*=-1;
		if(mp[{x[i],0}]==0){
			mp[{x[i],0}]=idxx++;
			inter[idxx-1]={x[i],0};
		}
	}
	for(int i=0;i<m;i++){
		l[i]=L[i];
		r[i]=R[i];
		y[i]=Y[i];
		if(r[i]-l[i]>100)
			srts[i]={-y[i],{x[l[i]],x[r[i]]}};
		else{
			srts[i]={1,{-1,-1}};
			int lst=-1;
			for(int j=l[i];j<=r[i];j++){
				if(h[j]<y[i])
					continue;
				int xx=mp[{x[j],y[i]}];
				if(xx==0){
					mp[{x[j],y[i]}]=xx=idxx++;
					inter[idxx-1]={x[j],y[i]};
					vec[x[j]].PB(y[i]);
				}
				if(~lst){
					v[lst].PB(xx);
					v[xx].PB(lst);
				}
				lst=xx;
			}
		}
	}
	sort(srts,srts+m);
	set<int> curst;
	int idx=0;
	for(int i=0;i<m;i++){
		if(srts[i].F==1)
			break;
		srts[i].F=-srts[i].F;
		while(idx<n&&srtb[idx].F>=srts[i].F)
			curst.insert(srtb[idx++].S);
		int lst=-1;
		for(set<int>::iterator j=curst.lower_bound(srts[i].S.F);j!=curst.end()&&(*j)<=srts[i].S.S;j++){
			int xx=mp[{(*j),srts[i].F}];
			if(xx==0){
				mp[{(*j),srts[i].F}]=xx=idxx++;
				inter[idxx-1]={(*j),srts[i].F};
				vec[(*j)].PB(srts[i].F);
			}
			if(~lst){
				v[lst].PB(xx);
				v[xx].PB(lst);
			}
			lst=xx;
		}
	}
	for(int i=0;i<n;i++){
		sort(vec[x[i]].begin(),vec[x[i]].end());
		for(int j=1;j<vec[x[i]].size();j++){
			v[mp[{x[i],vec[x[i]][j]}]].PB(mp[{x[i],vec[x[i]][j-1]}]);
			v[mp[{x[i],vec[x[i]][j-1]}]].PB(mp[{x[i],vec[x[i]][j]}]);
		}
	}
	return dijk();
}

Compilation message

walk.cpp: In function 'LL dijk()':
walk.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0;i<v[idx].size();i++){
      |               ~^~~~~~~~~~~~~~
walk.cpp: In function 'LL min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:126:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |   for(int j=1;j<vec[x[i]].size();j++){
      |               ~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 117836 KB Output is correct
2 Correct 55 ms 117776 KB Output is correct
3 Correct 49 ms 117684 KB Output is correct
4 Correct 55 ms 117712 KB Output is correct
5 Correct 53 ms 117836 KB Output is correct
6 Correct 51 ms 117828 KB Output is correct
7 Correct 51 ms 117716 KB Output is correct
8 Correct 57 ms 117788 KB Output is correct
9 Correct 50 ms 117744 KB Output is correct
10 Correct 51 ms 117856 KB Output is correct
11 Correct 54 ms 117772 KB Output is correct
12 Correct 51 ms 117764 KB Output is correct
13 Correct 51 ms 117724 KB Output is correct
14 Correct 52 ms 117716 KB Output is correct
15 Correct 51 ms 117680 KB Output is correct
16 Correct 55 ms 117752 KB Output is correct
17 Correct 52 ms 117744 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 117708 KB Output is correct
2 Correct 51 ms 117684 KB Output is correct
3 Correct 1060 ms 208276 KB Output is correct
4 Correct 1673 ms 231628 KB Output is correct
5 Correct 1216 ms 222272 KB Output is correct
6 Correct 1121 ms 213436 KB Output is correct
7 Correct 1205 ms 222268 KB Output is correct
8 Correct 1442 ms 231084 KB Output is correct
9 Correct 1256 ms 214800 KB Output is correct
10 Correct 2133 ms 265856 KB Output is correct
11 Correct 746 ms 175360 KB Output is correct
12 Correct 616 ms 173380 KB Output is correct
13 Correct 1817 ms 251192 KB Output is correct
14 Correct 511 ms 176112 KB Output is correct
15 Correct 584 ms 177328 KB Output is correct
16 Correct 627 ms 174972 KB Output is correct
17 Correct 623 ms 169576 KB Output is correct
18 Correct 447 ms 171716 KB Output is correct
19 Correct 70 ms 120496 KB Output is correct
20 Correct 253 ms 146648 KB Output is correct
21 Correct 545 ms 165844 KB Output is correct
22 Correct 563 ms 172592 KB Output is correct
23 Correct 700 ms 184720 KB Output is correct
24 Correct 659 ms 175304 KB Output is correct
25 Correct 568 ms 168692 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 129908 KB Output is correct
2 Execution timed out 4117 ms 818168 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 129908 KB Output is correct
2 Execution timed out 4117 ms 818168 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 117836 KB Output is correct
2 Correct 55 ms 117776 KB Output is correct
3 Correct 49 ms 117684 KB Output is correct
4 Correct 55 ms 117712 KB Output is correct
5 Correct 53 ms 117836 KB Output is correct
6 Correct 51 ms 117828 KB Output is correct
7 Correct 51 ms 117716 KB Output is correct
8 Correct 57 ms 117788 KB Output is correct
9 Correct 50 ms 117744 KB Output is correct
10 Correct 51 ms 117856 KB Output is correct
11 Correct 54 ms 117772 KB Output is correct
12 Correct 51 ms 117764 KB Output is correct
13 Correct 51 ms 117724 KB Output is correct
14 Correct 52 ms 117716 KB Output is correct
15 Correct 51 ms 117680 KB Output is correct
16 Correct 55 ms 117752 KB Output is correct
17 Correct 52 ms 117744 KB Output is correct
18 Correct 51 ms 117708 KB Output is correct
19 Correct 51 ms 117684 KB Output is correct
20 Correct 1060 ms 208276 KB Output is correct
21 Correct 1673 ms 231628 KB Output is correct
22 Correct 1216 ms 222272 KB Output is correct
23 Correct 1121 ms 213436 KB Output is correct
24 Correct 1205 ms 222268 KB Output is correct
25 Correct 1442 ms 231084 KB Output is correct
26 Correct 1256 ms 214800 KB Output is correct
27 Correct 2133 ms 265856 KB Output is correct
28 Correct 746 ms 175360 KB Output is correct
29 Correct 616 ms 173380 KB Output is correct
30 Correct 1817 ms 251192 KB Output is correct
31 Correct 511 ms 176112 KB Output is correct
32 Correct 584 ms 177328 KB Output is correct
33 Correct 627 ms 174972 KB Output is correct
34 Correct 623 ms 169576 KB Output is correct
35 Correct 447 ms 171716 KB Output is correct
36 Correct 70 ms 120496 KB Output is correct
37 Correct 253 ms 146648 KB Output is correct
38 Correct 545 ms 165844 KB Output is correct
39 Correct 563 ms 172592 KB Output is correct
40 Correct 700 ms 184720 KB Output is correct
41 Correct 659 ms 175304 KB Output is correct
42 Correct 568 ms 168692 KB Output is correct
43 Correct 175 ms 129908 KB Output is correct
44 Execution timed out 4117 ms 818168 KB Time limit exceeded
45 Halted 0 ms 0 KB -