oj.uz

Submission #378930

# Submission time Handle Problem Language Result Execution time Memory
378930 2021-03-17T07:44:36 Z autumn_eel Sky Walking (IOI19_walk) C++14
14 / 100
 3890 ms 546436 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,int 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();
	
	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,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]);
		}
	}

	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:50: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]
   50 |   while(cur<V.size()&&V[cur].first>=p.y){
      |         ~~~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 62956 KB Output is correct
2 Correct 42 ms 62956 KB Output is correct
3 Correct 48 ms 62956 KB Output is correct
4 Incorrect 42 ms 62956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 63084 KB Output is correct
2 Correct 41 ms 62956 KB Output is correct
3 Correct 2243 ms 202376 KB Output is correct
4 Correct 1988 ms 214488 KB Output is correct
5 Correct 1542 ms 195608 KB Output is correct
6 Correct 1278 ms 179380 KB Output is correct
7 Correct 1501 ms 195680 KB Output is correct
8 Correct 2935 ms 241220 KB Output is correct
9 Correct 1688 ms 192224 KB Output is correct
10 Correct 2808 ms 274320 KB Output is correct
11 Correct 1063 ms 136932 KB Output is correct
12 Correct 693 ms 112736 KB Output is correct
13 Correct 2386 ms 248132 KB Output is correct
14 Correct 516 ms 111712 KB Output is correct
15 Correct 585 ms 112088 KB Output is correct
16 Correct 596 ms 112732 KB Output is correct
17 Correct 618 ms 111072 KB Output is correct
18 Correct 489 ms 110724 KB Output is correct
19 Correct 57 ms 65388 KB Output is correct
20 Correct 239 ms 87012 KB Output is correct
21 Correct 609 ms 108488 KB Output is correct
22 Correct 582 ms 112096 KB Output is correct
23 Correct 558 ms 123792 KB Output is correct
24 Correct 575 ms 111840 KB Output is correct
25 Correct 668 ms 110560 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 77416 KB Output is correct
2 Runtime error 3890 ms 546436 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 217 ms 77416 KB Output is correct
2 Runtime error 3890 ms 546436 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 46 ms 62956 KB Output is correct
2 Correct 42 ms 62956 KB Output is correct
3 Correct 48 ms 62956 KB Output is correct
4 Incorrect 42 ms 62956 KB Output isn't correct
5 Halted 0 ms 0 KB -