oj.uz

Submission #378941

# Submission time Handle Problem Language Result Execution time Memory
378941 2021-03-17T07:51:57 Z autumn_eel Sky Walking (IOI19_walk) C++14
14 / 100
 4000 ms 511456 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();

	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,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 43 ms 62976 KB Output is correct
2 Correct 45 ms 62956 KB Output is correct
3 Correct 47 ms 63084 KB Output is correct
4 Incorrect 41 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 43 ms 63084 KB Output is correct
2 Correct 45 ms 62956 KB Output is correct
3 Correct 2205 ms 200748 KB Output is correct
4 Correct 1992 ms 211092 KB Output is correct
5 Correct 1545 ms 192232 KB Output is correct
6 Correct 1347 ms 176160 KB Output is correct
7 Correct 1496 ms 192384 KB Output is correct
8 Correct 2906 ms 239284 KB Output is correct
9 Correct 1689 ms 188896 KB Output is correct
10 Correct 2919 ms 270772 KB Output is correct
11 Correct 1123 ms 134808 KB Output is correct
12 Correct 728 ms 109464 KB Output is correct
13 Correct 2548 ms 244780 KB Output is correct
14 Correct 539 ms 108452 KB Output is correct
15 Correct 575 ms 109408 KB Output is correct
16 Correct 603 ms 110560 KB Output is correct
17 Correct 607 ms 109136 KB Output is correct
18 Correct 493 ms 108524 KB Output is correct
19 Correct 57 ms 65388 KB Output is correct
20 Correct 263 ms 85732 KB Output is correct
21 Correct 613 ms 106592 KB Output is correct
22 Correct 641 ms 109664 KB Output is correct
23 Correct 559 ms 121568 KB Output is correct
24 Correct 587 ms 109792 KB Output is correct
25 Correct 630 ms 108768 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 77288 KB Output is correct
2 Execution timed out 4103 ms 511456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 77288 KB Output is correct
2 Execution timed out 4103 ms 511456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 62976 KB Output is correct
2 Correct 45 ms 62956 KB Output is correct
3 Correct 47 ms 63084 KB Output is correct
4 Incorrect 41 ms 62956 KB Output isn't correct
5 Halted 0 ms 0 KB -