oj.uz

Submission #378962

# Submission time Handle Problem Language Result Execution time Memory
378962 2021-03-17T07:59:56 Z autumn_eel Sky Walking (IOI19_walk) C++14
24 / 100
 3865 ms 545748 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;

const ll INFL=0x3f3f3f3f3f3f3f3f;

struct st{
	int l,r,y;
};

static map<P,int>mp;
static ll d[2000000];
static int cnt=0;
static vector<P>E[2000000];

void add_edge(P a,P b,ll dist){
	if(!mp.count(a)){
		mp[a]=cnt++;
	}
	if(!mp.count(b)){
		mp[b]=cnt++;
	}
	E[mp[a]].push_back(P(dist,mp[b]));
	E[mp[b]].push_back(P(dist,mp[a]));
}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n=x.size();
	int m=l.size();

	mp.clear();
	cnt=0;
	rep(i,n)E[i].clear();
	
	vector<st>H;
	rep(i,m){
		H.push_back({l[i],r[i],y[i]});
	}
	sort(H.begin(),H.end(),[](st a,st b){return a.y>b.y;});

	vector<P>V;
	rep(i,n){
		V.push_back(P(h[i],i));
	}
	sort(V.begin(),V.end(),[](P a,P b){return a.first>b.first;});

	set<int>se;
	int cur=0;
	
	for(auto&p:H){
		while(cur<V.size()&&V[cur].first>=p.y){
			se.insert(V[cur].second);
			cur++;
		}
		auto it=se.lower_bound(p.l);
		while(it!=se.end()&&*it<p.r){
			int L=*it;
			it++;
			int R=*it;
			add_edge(P(L,p.y),P(R,p.y),x[R]-x[L]);
		}
	}

	map<int,vector<int>>mp_v;
	mp_v[s].push_back(0);
	mp_v[g].push_back(0);
	
	for(auto&p:mp){
		mp_v[p.first.first].push_back(p.first.second);
	}

	for(auto&v:mp_v){
		rep(i,int(v.second.size())-1){
			add_edge(P(v.first,v.second[i]),P(v.first,v.second[i+1]),v.second[i+1]-v.second[i]);
		}
	}

	if(!mp.count(P(s,0))||!mp.count(P(g,0)))return -1;

	
	priority_queue<P,vector<P>,greater<P>>que;
	memset(d,0x3f,sizeof(d));
	
	d[mp[P(s,0)]]=0;
	que.push(P(0,mp[P(s,0)]));

	while(!que.empty()){
		P p=que.top();que.pop();
		if(d[p.second]!=p.first)continue;

		for(P&u:E[p.second]){
			if(d[u.second]>p.first+u.first){
				d[u.second]=p.first+u.first;
				que.push(P(d[u.second],u.second));
			}
		}
	}

	ll ans=d[mp[P(g,0)]];
	
	if(ans==INFL)return -1;
	return ans;
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:54:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   while(cur<V.size()&&V[cur].first>=p.y){
      |         ~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 62956 KB Output is correct
2 Correct 41 ms 62956 KB Output is correct
3 Correct 45 ms 62956 KB Output is correct
4 Correct 32 ms 47340 KB Output is correct
5 Correct 42 ms 63084 KB Output is correct
6 Correct 42 ms 63084 KB Output is correct
7 Correct 43 ms 63084 KB Output is correct
8 Correct 43 ms 63084 KB Output is correct
9 Correct 48 ms 62956 KB Output is correct
10 Correct 43 ms 63084 KB Output is correct
11 Correct 44 ms 63084 KB Output is correct
12 Correct 41 ms 62956 KB Output is correct
13 Correct 41 ms 62956 KB Output is correct
14 Correct 41 ms 62956 KB Output is correct
15 Correct 34 ms 47340 KB Output is correct
16 Correct 41 ms 62956 KB Output is correct
17 Correct 42 ms 63084 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 62956 KB Output is correct
2 Correct 47 ms 62956 KB Output is correct
3 Correct 2225 ms 202596 KB Output is correct
4 Correct 1985 ms 213648 KB Output is correct
5 Correct 1581 ms 194912 KB Output is correct
6 Correct 1339 ms 178948 KB Output is correct
7 Correct 1492 ms 195232 KB Output is correct
8 Correct 3098 ms 241044 KB Output is correct
9 Correct 1885 ms 191860 KB Output is correct
10 Correct 2904 ms 273580 KB Output is correct
11 Correct 1096 ms 136548 KB Output is correct
12 Correct 741 ms 112256 KB Output is correct
13 Correct 2455 ms 247800 KB Output is correct
14 Correct 533 ms 95576 KB Output is correct
15 Correct 708 ms 111796 KB Output is correct
16 Correct 719 ms 112480 KB Output is correct
17 Correct 590 ms 110560 KB Output is correct
18 Correct 498 ms 110104 KB Output is correct
19 Correct 56 ms 65388 KB Output is correct
20 Correct 268 ms 86884 KB Output is correct
21 Correct 603 ms 108300 KB Output is correct
22 Correct 594 ms 111584 KB Output is correct
23 Correct 603 ms 123360 KB Output is correct
24 Correct 558 ms 111456 KB Output is correct
25 Correct 639 ms 110244 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 77332 KB Output is correct
2 Runtime error 3865 ms 545748 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 77332 KB Output is correct
2 Runtime error 3865 ms 545748 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 62956 KB Output is correct
2 Correct 41 ms 62956 KB Output is correct
3 Correct 45 ms 62956 KB Output is correct
4 Correct 32 ms 47340 KB Output is correct
5 Correct 42 ms 63084 KB Output is correct
6 Correct 42 ms 63084 KB Output is correct
7 Correct 43 ms 63084 KB Output is correct
8 Correct 43 ms 63084 KB Output is correct
9 Correct 48 ms 62956 KB Output is correct
10 Correct 43 ms 63084 KB Output is correct
11 Correct 44 ms 63084 KB Output is correct
12 Correct 41 ms 62956 KB Output is correct
13 Correct 41 ms 62956 KB Output is correct
14 Correct 41 ms 62956 KB Output is correct
15 Correct 34 ms 47340 KB Output is correct
16 Correct 41 ms 62956 KB Output is correct
17 Correct 42 ms 63084 KB Output is correct
18 Correct 47 ms 62956 KB Output is correct
19 Correct 47 ms 62956 KB Output is correct
20 Correct 2225 ms 202596 KB Output is correct
21 Correct 1985 ms 213648 KB Output is correct
22 Correct 1581 ms 194912 KB Output is correct
23 Correct 1339 ms 178948 KB Output is correct
24 Correct 1492 ms 195232 KB Output is correct
25 Correct 3098 ms 241044 KB Output is correct
26 Correct 1885 ms 191860 KB Output is correct
27 Correct 2904 ms 273580 KB Output is correct
28 Correct 1096 ms 136548 KB Output is correct
29 Correct 741 ms 112256 KB Output is correct
30 Correct 2455 ms 247800 KB Output is correct
31 Correct 533 ms 95576 KB Output is correct
32 Correct 708 ms 111796 KB Output is correct
33 Correct 719 ms 112480 KB Output is correct
34 Correct 590 ms 110560 KB Output is correct
35 Correct 498 ms 110104 KB Output is correct
36 Correct 56 ms 65388 KB Output is correct
37 Correct 268 ms 86884 KB Output is correct
38 Correct 603 ms 108300 KB Output is correct
39 Correct 594 ms 111584 KB Output is correct
40 Correct 603 ms 123360 KB Output is correct
41 Correct 558 ms 111456 KB Output is correct
42 Correct 639 ms 110244 KB Output is correct
43 Correct 214 ms 77332 KB Output is correct
44 Runtime error 3865 ms 545748 KB Execution killed with signal 6
45 Halted 0 ms 0 KB -