oj.uz

Submission #762006

# Submission time Handle Problem Language Result Execution time Memory
762006 2023-06-20T14:15:16 Z aihay Sky Walking (IOI19_walk) C++14
24 / 100
 4000 ms 532588 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;

LL n,m,s,g,x[100010],h[100010],l[100010],r[100010],y[100010],idxx;
pair<LL,LL> srtb[100010];
pair<LL,pair<LL,LL>> srts[100010];
LL cst[1000010];
vector<LL> v[5000010];
map<pair<LL,LL>,LL> mp;
map<LL,LL> comp;
LL dcomp[100010];
pair<LL,LL> inter[5000010];
LL dijk(){
	for(int i=0;i<idxx;i++)
		cst[i]=MAAX;
	priority_queue<pair<LL,LL>> pq;
	pq.push({0,mp[{x[s],0}]});
	while(pq.size()){
		LL cost=-pq.top().F,idx=pq.top().S;
		pq.pop();
		if(cost>cst[idx])
			continue;
		cst[idx]=cost;
		if(idx==mp[{x[g],0}])
			break;
		for(int i=0;i<v[idx].size();i++){
			LL x1=inter[idx].F,x2=inter[v[idx][i]].F;
			LL y1=inter[idx].S,y2=inter[v[idx][i]].S;
			LL ncst=cost+abs(x2-x1)+abs(y2-y1);
			LL nidx=v[idx][i];
			if(ncst<cst[nidx]){
				cst[nidx]=ncst;
				pq.push({-ncst,nidx});
			}
		}
	}
	if(cst[mp[{x[g],0}]]==MAAX)
		cst[mp[{x[g],0}]]=-1;
	return cst[mp[{x[g],0}]];
}
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];
		comp[x[i]]=i;
		h[i]=H[i];
		vec[x[i]].PB(0);
		srtb[i]={-h[i],x[i]};
	}
	sort(srtb,srtb+n);
	mp[{x[s],0}]=idxx++;
	inter[0]={x[s],0};
	mp[{x[g],0}]=idxx++;
	inter[1]={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];
		srts[i]={-y[i],{x[l[i]],x[r[i]]}};
	}
	sort(srts,srts+m);
	set<int> curst;
	int idx=0;
	for(int i=0;i<m;i++){
		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++){
			if(mp[{(*j),srts[i].F}]==0){
				mp[{(*j),srts[i].F}]=idxx++;
				inter[idxx-1]={(*j),srts[i].F};
			}
			if(~lst){
				v[mp[{lst,srts[i].F}]].PB(mp[{(*j),srts[i].F}]);
				v[mp[{(*j),srts[i].F}]].PB(mp[{lst,srts[i].F}]);
			}
			vec[(*j)].PB(srts[i].F);
			lst=(*j);
		}
	}
	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;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc=1;
    // cin>>tc;
    while(tc--){
		cin>>N>>M;
		for(int i=0;i<N;i++){
			int x;
			cin>>x;
			X.PB(x);
		}
		for(int i=0;i<N;i++){
			int x;
			cin>>x;
			H.PB(x);
		}
		for(int i=0;i<M;i++){
			int x;
			cin>>x;
			L.PB(x);
		}
		for(int i=0;i<M;i++){
			int x;
			cin>>x;
			R.PB(x);
		}
		for(int i=0;i<M;i++){
			int x;
			cin>>x;
			Y.PB(x);
		}
		cin>>S>>G;
		cout<<min_distance(X,H,L,R,Y,S,G);
    }
    return 0;
}*/

Compilation message

walk.cpp: In function 'LL dijk()':
walk.cpp:36:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   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:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int j=1;j<vec[x[i]].size();j++){
      |               ~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117732 KB Output is correct
2 Correct 49 ms 117676 KB Output is correct
3 Correct 51 ms 117704 KB Output is correct
4 Correct 52 ms 117736 KB Output is correct
5 Correct 54 ms 117820 KB Output is correct
6 Correct 58 ms 117808 KB Output is correct
7 Correct 56 ms 117964 KB Output is correct
8 Correct 50 ms 117752 KB Output is correct
9 Correct 53 ms 117844 KB Output is correct
10 Correct 51 ms 117784 KB Output is correct
11 Correct 52 ms 117708 KB Output is correct
12 Correct 59 ms 117780 KB Output is correct
13 Correct 51 ms 117708 KB Output is correct
14 Correct 50 ms 117676 KB Output is correct
15 Correct 49 ms 117720 KB Output is correct
16 Correct 51 ms 117748 KB Output is correct
17 Correct 51 ms 117856 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 58 ms 117696 KB Output is correct
3 Correct 1560 ms 243776 KB Output is correct
4 Correct 2049 ms 274620 KB Output is correct
5 Correct 1515 ms 257416 KB Output is correct
6 Correct 1435 ms 244180 KB Output is correct
7 Correct 1532 ms 257500 KB Output is correct
8 Correct 2245 ms 277432 KB Output is correct
9 Correct 1828 ms 250924 KB Output is correct
10 Correct 3129 ms 324116 KB Output is correct
11 Correct 1063 ms 195436 KB Output is correct
12 Correct 964 ms 188940 KB Output is correct
13 Correct 2574 ms 302296 KB Output is correct
14 Correct 620 ms 186888 KB Output is correct
15 Correct 578 ms 188976 KB Output is correct
16 Correct 595 ms 188220 KB Output is correct
17 Correct 617 ms 186004 KB Output is correct
18 Correct 554 ms 187260 KB Output is correct
19 Correct 71 ms 121256 KB Output is correct
20 Correct 288 ms 152120 KB Output is correct
21 Correct 535 ms 181036 KB Output is correct
22 Correct 510 ms 188708 KB Output is correct
23 Correct 710 ms 199356 KB Output is correct
24 Correct 608 ms 187392 KB Output is correct
25 Correct 575 ms 184892 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 136480 KB Output is correct
2 Execution timed out 4070 ms 532588 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 136480 KB Output is correct
2 Execution timed out 4070 ms 532588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117732 KB Output is correct
2 Correct 49 ms 117676 KB Output is correct
3 Correct 51 ms 117704 KB Output is correct
4 Correct 52 ms 117736 KB Output is correct
5 Correct 54 ms 117820 KB Output is correct
6 Correct 58 ms 117808 KB Output is correct
7 Correct 56 ms 117964 KB Output is correct
8 Correct 50 ms 117752 KB Output is correct
9 Correct 53 ms 117844 KB Output is correct
10 Correct 51 ms 117784 KB Output is correct
11 Correct 52 ms 117708 KB Output is correct
12 Correct 59 ms 117780 KB Output is correct
13 Correct 51 ms 117708 KB Output is correct
14 Correct 50 ms 117676 KB Output is correct
15 Correct 49 ms 117720 KB Output is correct
16 Correct 51 ms 117748 KB Output is correct
17 Correct 51 ms 117856 KB Output is correct
18 Correct 51 ms 117708 KB Output is correct
19 Correct 58 ms 117696 KB Output is correct
20 Correct 1560 ms 243776 KB Output is correct
21 Correct 2049 ms 274620 KB Output is correct
22 Correct 1515 ms 257416 KB Output is correct
23 Correct 1435 ms 244180 KB Output is correct
24 Correct 1532 ms 257500 KB Output is correct
25 Correct 2245 ms 277432 KB Output is correct
26 Correct 1828 ms 250924 KB Output is correct
27 Correct 3129 ms 324116 KB Output is correct
28 Correct 1063 ms 195436 KB Output is correct
29 Correct 964 ms 188940 KB Output is correct
30 Correct 2574 ms 302296 KB Output is correct
31 Correct 620 ms 186888 KB Output is correct
32 Correct 578 ms 188976 KB Output is correct
33 Correct 595 ms 188220 KB Output is correct
34 Correct 617 ms 186004 KB Output is correct
35 Correct 554 ms 187260 KB Output is correct
36 Correct 71 ms 121256 KB Output is correct
37 Correct 288 ms 152120 KB Output is correct
38 Correct 535 ms 181036 KB Output is correct
39 Correct 510 ms 188708 KB Output is correct
40 Correct 710 ms 199356 KB Output is correct
41 Correct 608 ms 187392 KB Output is correct
42 Correct 575 ms 184892 KB Output is correct
43 Correct 175 ms 136480 KB Output is correct
44 Execution timed out 4070 ms 532588 KB Time limit exceeded
45 Halted 0 ms 0 KB -