oj.uz

Submission #762320

# Submission time Handle Problem Language Result Execution time Memory
762320 2023-06-21T10:13:52 Z aihay Sky Walking (IOI19_walk) C++14
10 / 100
 1564 ms 295280 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[1000010];
map<pair<int,int>,int> mp;
pair<int,int> inter[1000010];
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]>500)
			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();
}
int N,M,S,G;
vector<int> X,H,L,R,Y;

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 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23804 KB Output is correct
5 Correct 12 ms 23808 KB Output is correct
6 Correct 12 ms 23804 KB Output is correct
7 Correct 12 ms 23812 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 12 ms 23808 KB Output is correct
10 Correct 12 ms 23948 KB Output is correct
11 Correct 12 ms 23804 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23836 KB Output is correct
14 Correct 12 ms 23868 KB Output is correct
15 Correct 11 ms 23804 KB Output is correct
16 Correct 12 ms 23828 KB Output is correct
17 Correct 12 ms 23892 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23808 KB Output is correct
3 Correct 1059 ms 114064 KB Output is correct
4 Correct 1564 ms 135464 KB Output is correct
5 Correct 1096 ms 126484 KB Output is correct
6 Correct 1082 ms 117668 KB Output is correct
7 Correct 1171 ms 126440 KB Output is correct
8 Correct 1446 ms 136576 KB Output is correct
9 Correct 1291 ms 118316 KB Output is correct
10 Runtime error 1088 ms 295280 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 35844 KB Output is correct
2 Runtime error 698 ms 274016 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 113 ms 35844 KB Output is correct
2 Runtime error 698 ms 274016 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 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23804 KB Output is correct
5 Correct 12 ms 23808 KB Output is correct
6 Correct 12 ms 23804 KB Output is correct
7 Correct 12 ms 23812 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 12 ms 23808 KB Output is correct
10 Correct 12 ms 23948 KB Output is correct
11 Correct 12 ms 23804 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23836 KB Output is correct
14 Correct 12 ms 23868 KB Output is correct
15 Correct 11 ms 23804 KB Output is correct
16 Correct 12 ms 23828 KB Output is correct
17 Correct 12 ms 23892 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct
19 Correct 11 ms 23808 KB Output is correct
20 Correct 1059 ms 114064 KB Output is correct
21 Correct 1564 ms 135464 KB Output is correct
22 Correct 1096 ms 126484 KB Output is correct
23 Correct 1082 ms 117668 KB Output is correct
24 Correct 1171 ms 126440 KB Output is correct
25 Correct 1446 ms 136576 KB Output is correct
26 Correct 1291 ms 118316 KB Output is correct
27 Runtime error 1088 ms 295280 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -