oj.uz

Submission #761521

# Submission time Handle Problem Language Result Execution time Memory
761521 2023-06-19T21:56:47 Z aihay Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 548608 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;
LL cst[1000010];
vector<int> v[5000010];
map<pair<LL,LL>,int> mp;
pair<LL,LL> inter[5000010];
int tim;
LL dijk(){
	for(int i=0;i<idxx;i++)
		cst[i]=MAAX;
	priority_queue<pair<LL,int>> pq;
	pq.push({0,mp[{x[s],0}]});
	while(pq.size()&&time(0)-tim<3){
		LL cost=-pq.top().F;
		int 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++){
			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[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){
	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);
	}
	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++){
		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];
		int lst=-1;
		for(int j=l[i];j<=r[i];j++){
			if(h[j]<y[i])
				continue;
			if(mp[{x[j],y[i]}]==0){
				mp[{x[j],y[i]}]=idxx++;
				inter[idxx-1]={x[j],y[i]};
			}
			if(~lst){
				v[mp[{x[lst],y[i]}]].PB(mp[{x[j],y[i]}]);
				v[mp[{x[j],y[i]}]].PB(mp[{x[lst],y[i]}]);
			}
			vec[x[j]].PB(y[i]);
			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();
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117708 KB Output is correct
2 Correct 54 ms 117656 KB Output is correct
3 Correct 52 ms 117720 KB Output is correct
4 Correct 55 ms 117716 KB Output is correct
5 Correct 55 ms 117708 KB Output is correct
6 Correct 54 ms 117748 KB Output is correct
7 Correct 55 ms 117744 KB Output is correct
8 Correct 56 ms 117684 KB Output is correct
9 Correct 55 ms 117740 KB Output is correct
10 Correct 59 ms 117928 KB Output is correct
11 Correct 55 ms 117644 KB Output is correct
12 Correct 54 ms 117644 KB Output is correct
13 Correct 55 ms 117744 KB Output is correct
14 Correct 58 ms 117660 KB Output is correct
15 Correct 55 ms 117724 KB Output is correct
16 Correct 53 ms 117652 KB Output is correct
17 Correct 55 ms 117796 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117740 KB Output is correct
2 Correct 55 ms 117672 KB Output is correct
3 Correct 1391 ms 210480 KB Output is correct
4 Correct 1841 ms 232036 KB Output is correct
5 Correct 1412 ms 217760 KB Output is correct
6 Correct 2005 ms 208448 KB Output is correct
7 Correct 1392 ms 217932 KB Output is correct
8 Correct 1794 ms 234920 KB Output is correct
9 Correct 1510 ms 214256 KB Output is correct
10 Correct 2505 ms 267748 KB Output is correct
11 Correct 805 ms 173892 KB Output is correct
12 Correct 686 ms 169772 KB Output is correct
13 Correct 2227 ms 252884 KB Output is correct
14 Correct 3339 ms 168192 KB Output is correct
15 Correct 2053 ms 169712 KB Output is correct
16 Correct 754 ms 168960 KB Output is correct
17 Correct 771 ms 167232 KB Output is correct
18 Execution timed out 4083 ms 150248 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 131036 KB Output is correct
2 Execution timed out 4099 ms 548608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 131036 KB Output is correct
2 Execution timed out 4099 ms 548608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117708 KB Output is correct
2 Correct 54 ms 117656 KB Output is correct
3 Correct 52 ms 117720 KB Output is correct
4 Correct 55 ms 117716 KB Output is correct
5 Correct 55 ms 117708 KB Output is correct
6 Correct 54 ms 117748 KB Output is correct
7 Correct 55 ms 117744 KB Output is correct
8 Correct 56 ms 117684 KB Output is correct
9 Correct 55 ms 117740 KB Output is correct
10 Correct 59 ms 117928 KB Output is correct
11 Correct 55 ms 117644 KB Output is correct
12 Correct 54 ms 117644 KB Output is correct
13 Correct 55 ms 117744 KB Output is correct
14 Correct 58 ms 117660 KB Output is correct
15 Correct 55 ms 117724 KB Output is correct
16 Correct 53 ms 117652 KB Output is correct
17 Correct 55 ms 117796 KB Output is correct
18 Correct 55 ms 117740 KB Output is correct
19 Correct 55 ms 117672 KB Output is correct
20 Correct 1391 ms 210480 KB Output is correct
21 Correct 1841 ms 232036 KB Output is correct
22 Correct 1412 ms 217760 KB Output is correct
23 Correct 2005 ms 208448 KB Output is correct
24 Correct 1392 ms 217932 KB Output is correct
25 Correct 1794 ms 234920 KB Output is correct
26 Correct 1510 ms 214256 KB Output is correct
27 Correct 2505 ms 267748 KB Output is correct
28 Correct 805 ms 173892 KB Output is correct
29 Correct 686 ms 169772 KB Output is correct
30 Correct 2227 ms 252884 KB Output is correct
31 Correct 3339 ms 168192 KB Output is correct
32 Correct 2053 ms 169712 KB Output is correct
33 Correct 754 ms 168960 KB Output is correct
34 Correct 771 ms 167232 KB Output is correct
35 Execution timed out 4083 ms 150248 KB Time limit exceeded
36 Halted 0 ms 0 KB -