oj.uz

Submission #378951

# Submission time Handle Problem Language Result Execution time Memory
378951 2021-03-17T07:55:13 Z autumn_eel Sky Walking (IOI19_walk) C++14
14 / 100
 3958 ms 546228 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]);
		}
	}

	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62956 KB Output is correct
2 Correct 37 ms 62956 KB Output is correct
3 Correct 38 ms 62956 KB Output is correct
4 Incorrect 37 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 39 ms 62956 KB Output is correct
2 Correct 38 ms 62956 KB Output is correct
3 Correct 2212 ms 201060 KB Output is correct
4 Correct 2073 ms 211116 KB Output is correct
5 Correct 1432 ms 192556 KB Output is correct
6 Correct 1352 ms 176456 KB Output is correct
7 Correct 1448 ms 192680 KB Output is correct
8 Correct 2959 ms 239520 KB Output is correct
9 Correct 1660 ms 189396 KB Output is correct
10 Correct 2992 ms 271160 KB Output is correct
11 Correct 1297 ms 136268 KB Output is correct
12 Correct 814 ms 111000 KB Output is correct
13 Correct 2602 ms 246288 KB Output is correct
14 Correct 519 ms 109920 KB Output is correct
15 Correct 799 ms 110944 KB Output is correct
16 Correct 781 ms 112096 KB Output is correct
17 Correct 587 ms 110560 KB Output is correct
18 Correct 519 ms 110188 KB Output is correct
19 Correct 56 ms 65388 KB Output is correct
20 Correct 241 ms 87012 KB Output is correct
21 Correct 657 ms 107984 KB Output is correct
22 Correct 611 ms 111072 KB Output is correct
23 Correct 572 ms 123052 KB Output is correct
24 Correct 600 ms 110988 KB Output is correct
25 Correct 642 ms 110328 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 77380 KB Output is correct
2 Runtime error 3958 ms 546228 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 227 ms 77380 KB Output is correct
2 Runtime error 3958 ms 546228 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 37 ms 62956 KB Output is correct
2 Correct 37 ms 62956 KB Output is correct
3 Correct 38 ms 62956 KB Output is correct
4 Incorrect 37 ms 62956 KB Output isn't correct
5 Halted 0 ms 0 KB -