oj.uz

Submission #762335

# Submission time Handle Problem Language Result Execution time Memory
762335 2023-06-21T10:25:37 Z aihay Sky Walking (IOI19_walk) C++14
24 / 100
 2340 ms 535092 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,tim;
pair<int,int> srtb[100010];
pair<int,pair<int,int>> srts[100010];
LL cst[1000010];
vector<int> v[2000010];
map<pair<int,int>,int> mp;
pair<int,int> inter[2000010];
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){
	tim=time(0);
	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]>50)
			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||time(0)-tim>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=0;
			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:127:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for(int j=1;j<vec[x[i]].size();j++){
      |               ~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47316 KB Output is correct
2 Correct 22 ms 47240 KB Output is correct
3 Correct 21 ms 47280 KB Output is correct
4 Correct 20 ms 47268 KB Output is correct
5 Correct 21 ms 47288 KB Output is correct
6 Correct 21 ms 47316 KB Output is correct
7 Correct 21 ms 47280 KB Output is correct
8 Correct 22 ms 47316 KB Output is correct
9 Correct 22 ms 47232 KB Output is correct
10 Correct 22 ms 47316 KB Output is correct
11 Correct 23 ms 47316 KB Output is correct
12 Correct 22 ms 47340 KB Output is correct
13 Correct 21 ms 47232 KB Output is correct
14 Correct 21 ms 47268 KB Output is correct
15 Correct 22 ms 47316 KB Output is correct
16 Correct 22 ms 47332 KB Output is correct
17 Correct 22 ms 47376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 22 ms 47256 KB Output is correct
3 Correct 1086 ms 135792 KB Output is correct
4 Correct 1531 ms 157140 KB Output is correct
5 Correct 1129 ms 148304 KB Output is correct
6 Correct 1041 ms 139428 KB Output is correct
7 Correct 1118 ms 148412 KB Output is correct
8 Correct 1465 ms 158844 KB Output is correct
9 Correct 1344 ms 141552 KB Output is correct
10 Correct 2340 ms 192532 KB Output is correct
11 Correct 697 ms 102432 KB Output is correct
12 Correct 567 ms 98920 KB Output is correct
13 Correct 1823 ms 176732 KB Output is correct
14 Correct 478 ms 102004 KB Output is correct
15 Correct 541 ms 103608 KB Output is correct
16 Correct 614 ms 101756 KB Output is correct
17 Correct 621 ms 97232 KB Output is correct
18 Correct 387 ms 98804 KB Output is correct
19 Correct 35 ms 50004 KB Output is correct
20 Correct 205 ms 74284 KB Output is correct
21 Correct 535 ms 92700 KB Output is correct
22 Correct 538 ms 98840 KB Output is correct
23 Correct 655 ms 111556 KB Output is correct
24 Correct 583 ms 101836 KB Output is correct
25 Correct 551 ms 95588 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 58812 KB Output is correct
2 Runtime error 2252 ms 535092 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 58812 KB Output is correct
2 Runtime error 2252 ms 535092 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47316 KB Output is correct
2 Correct 22 ms 47240 KB Output is correct
3 Correct 21 ms 47280 KB Output is correct
4 Correct 20 ms 47268 KB Output is correct
5 Correct 21 ms 47288 KB Output is correct
6 Correct 21 ms 47316 KB Output is correct
7 Correct 21 ms 47280 KB Output is correct
8 Correct 22 ms 47316 KB Output is correct
9 Correct 22 ms 47232 KB Output is correct
10 Correct 22 ms 47316 KB Output is correct
11 Correct 23 ms 47316 KB Output is correct
12 Correct 22 ms 47340 KB Output is correct
13 Correct 21 ms 47232 KB Output is correct
14 Correct 21 ms 47268 KB Output is correct
15 Correct 22 ms 47316 KB Output is correct
16 Correct 22 ms 47332 KB Output is correct
17 Correct 22 ms 47376 KB Output is correct
18 Correct 21 ms 47316 KB Output is correct
19 Correct 22 ms 47256 KB Output is correct
20 Correct 1086 ms 135792 KB Output is correct
21 Correct 1531 ms 157140 KB Output is correct
22 Correct 1129 ms 148304 KB Output is correct
23 Correct 1041 ms 139428 KB Output is correct
24 Correct 1118 ms 148412 KB Output is correct
25 Correct 1465 ms 158844 KB Output is correct
26 Correct 1344 ms 141552 KB Output is correct
27 Correct 2340 ms 192532 KB Output is correct
28 Correct 697 ms 102432 KB Output is correct
29 Correct 567 ms 98920 KB Output is correct
30 Correct 1823 ms 176732 KB Output is correct
31 Correct 478 ms 102004 KB Output is correct
32 Correct 541 ms 103608 KB Output is correct
33 Correct 614 ms 101756 KB Output is correct
34 Correct 621 ms 97232 KB Output is correct
35 Correct 387 ms 98804 KB Output is correct
36 Correct 35 ms 50004 KB Output is correct
37 Correct 205 ms 74284 KB Output is correct
38 Correct 535 ms 92700 KB Output is correct
39 Correct 538 ms 98840 KB Output is correct
40 Correct 655 ms 111556 KB Output is correct
41 Correct 583 ms 101836 KB Output is correct
42 Correct 551 ms 95588 KB Output is correct
43 Correct 124 ms 58812 KB Output is correct
44 Runtime error 2252 ms 535092 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -