oj.uz

Submission #171869

# Submission time Handle Problem Language Result Execution time Memory
171869 2019-12-30T14:25:40 Z dsjong Sky Walking (IOI19_walk) C++14
24 / 100
 2281 ms 227084 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

unordered_map<long long,int> mp;
vector<pair<int,int>>adj[1000005];
long long dis[1000005];
long long INF=LONG_LONG_MAX;
bool vis[1000005];
void dijkstra(int source){
	class prioritize{
		public: bool operator ()(pair<int,long long>&p1 ,pair<int,long long>&p2){
			return p1.second>p2.second;
		}
	};
	for(int i=0;i<=1000000;i++) dis[i]=INF;
	priority_queue<pair<int,long long>,vector<pair<int,long long>>,prioritize>pq;
	dis[source]=0;
	pq.push({source,0});
	while(!pq.empty()){
		pair<int,long long>curr=pq.top();
		pq.pop();
		int cv=curr.first;
		long long cw=curr.second;
		if(vis[cv]) continue;
		vis[cv]=true; 
		for(auto i:adj[cv]){
			if(vis[i.first]) continue;
			if(i.second+cw<dis[i.first]){
				dis[i.first]=i.second+cw;
				//cout<<i.first<<" "<<dis[i.first]<<endl;
				pq.push({i.first,dis[i.first]});
			}
		}
	}
}
long long get(int x, int y){
	return (x*(1e9+1ll)+y);
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, std::vector<int> y, int s, int g) {
	vector<pair<int,int>>all;
	vector<pair<int,pair<int,int>>>v;
	int n = x.size(), m = l.size();
	for(int i=0;i<m;i++){
		v.push_back({y[i],{l[i],r[i]}});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<m;i++){
		y[i]=v[i].first;
		l[i]=v[i].second.first;
		r[i]=v[i].second.second;
	}
	set<int>se;
	for(int i=0;i<n;i++) se.insert(i);
	mp[get(s,0)]=0;
	mp[get(g,0)]=1;
	int cnt = 2;
	all.push_back({s,0});
	all.push_back({g,0});
	for(int i=0;i<m;i++){
		//cout<<y[i]<<" "<<l[i]<<" "<<r[i]<<": ";
		int last=-1, cur=0;
		while(cur<r[i]){
			auto it=se.lower_bound(max(last+1,l[i]));
			if(it==se.end()) break;
			cur=*it;
			if(h[cur]>=y[i]){
				all.push_back({cur,y[i]});
				//cout<<cur<<" "<<y[i]<<endl;
				if(!mp[get(cur,y[i])]) mp[get(cur,y[i])]=cnt++;
				if(last!=-1){
					adj[mp[get(cur,y[i])]].push_back({mp[get(last,y[i])],x[cur]-x[last]});
					adj[mp[get(last,y[i])]].push_back({mp[get(cur,y[i])],x[cur]-x[last]});
				}
				last=cur;
			}
			else{
				se.erase(it);
			}
		}
	}
	/*for(int i = 0; i < m; i++){
		int last=-1;
		for(int j = l[i]; j <= r[i]; j++){
			if(!mp[get(j, y[i])] && h[j] >= y[i]){
				all.push_back({j, y[i]});
				mp[get(j, y[i])] =cnt;
				//cout<<mp[{j,y[i]}]<<endl;
				cnt++;
			}
			if(h[j]>=y[i]){
				if(last!=-1){
					adj[mp[get(j,y[i])]].push_back({mp[get(last,y[i])],x[j]-x[last]});
					adj[mp[get(last,y[i])]].push_back({mp[get(j,y[i])],x[j]-x[last]});
					//cout<<mp[{j,y[i]}]<<" "<<mp[{last,y[i]}]<<" "<<x[j]-x[last]<<endl;
				}
				last = j;
			}
		}
	}*/
	sort(all.begin(),all.end());
	for(int i=1; i < all.size(); i++){
		if(all[i].first == all[i-1].first){
			adj[mp[get(all[i].first,all[i].second)]].push_back({mp[get(all[i-1].first,all[i-1].second)], all[i].second-all[i-1].second});
			adj[mp[get(all[i-1].first,all[i-1].second)]].push_back({mp[get(all[i].first,all[i].second)], all[i].second-all[i-1].second});
		}
	}
	dijkstra(0);
	if(dis[1]==INF) return -1;
	return dis[1];
}

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:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i < all.size(); i++){
               ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 30 ms 31612 KB Output is correct
3 Correct 30 ms 31608 KB Output is correct
4 Correct 30 ms 31608 KB Output is correct
5 Correct 31 ms 31736 KB Output is correct
6 Correct 31 ms 31736 KB Output is correct
7 Correct 32 ms 31736 KB Output is correct
8 Correct 31 ms 31736 KB Output is correct
9 Correct 30 ms 31608 KB Output is correct
10 Correct 31 ms 31736 KB Output is correct
11 Correct 30 ms 31608 KB Output is correct
12 Correct 31 ms 31736 KB Output is correct
13 Correct 30 ms 31608 KB Output is correct
14 Correct 30 ms 31608 KB Output is correct
15 Correct 30 ms 31608 KB Output is correct
16 Correct 30 ms 31608 KB Output is correct
17 Correct 31 ms 31736 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 30 ms 31624 KB Output is correct
3 Correct 1467 ms 116236 KB Output is correct
4 Correct 1554 ms 119784 KB Output is correct
5 Correct 1135 ms 105100 KB Output is correct
6 Correct 1014 ms 99752 KB Output is correct
7 Correct 1123 ms 108784 KB Output is correct
8 Correct 1890 ms 141672 KB Output is correct
9 Correct 1232 ms 109444 KB Output is correct
10 Correct 2281 ms 163236 KB Output is correct
11 Correct 826 ms 76600 KB Output is correct
12 Correct 503 ms 61592 KB Output is correct
13 Correct 1834 ms 142108 KB Output is correct
14 Correct 379 ms 56476 KB Output is correct
15 Correct 332 ms 56220 KB Output is correct
16 Correct 353 ms 57884 KB Output is correct
17 Correct 383 ms 56836 KB Output is correct
18 Correct 277 ms 63132 KB Output is correct
19 Correct 41 ms 32888 KB Output is correct
20 Correct 152 ms 43696 KB Output is correct
21 Correct 325 ms 58896 KB Output is correct
22 Correct 304 ms 60572 KB Output is correct
23 Correct 429 ms 64336 KB Output is correct
24 Correct 327 ms 59164 KB Output is correct
25 Correct 377 ms 58908 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 43864 KB Output is correct
2 Runtime error 937 ms 227084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 43864 KB Output is correct
2 Runtime error 937 ms 227084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 30 ms 31612 KB Output is correct
3 Correct 30 ms 31608 KB Output is correct
4 Correct 30 ms 31608 KB Output is correct
5 Correct 31 ms 31736 KB Output is correct
6 Correct 31 ms 31736 KB Output is correct
7 Correct 32 ms 31736 KB Output is correct
8 Correct 31 ms 31736 KB Output is correct
9 Correct 30 ms 31608 KB Output is correct
10 Correct 31 ms 31736 KB Output is correct
11 Correct 30 ms 31608 KB Output is correct
12 Correct 31 ms 31736 KB Output is correct
13 Correct 30 ms 31608 KB Output is correct
14 Correct 30 ms 31608 KB Output is correct
15 Correct 30 ms 31608 KB Output is correct
16 Correct 30 ms 31608 KB Output is correct
17 Correct 31 ms 31736 KB Output is correct
18 Correct 30 ms 31608 KB Output is correct
19 Correct 30 ms 31624 KB Output is correct
20 Correct 1467 ms 116236 KB Output is correct
21 Correct 1554 ms 119784 KB Output is correct
22 Correct 1135 ms 105100 KB Output is correct
23 Correct 1014 ms 99752 KB Output is correct
24 Correct 1123 ms 108784 KB Output is correct
25 Correct 1890 ms 141672 KB Output is correct
26 Correct 1232 ms 109444 KB Output is correct
27 Correct 2281 ms 163236 KB Output is correct
28 Correct 826 ms 76600 KB Output is correct
29 Correct 503 ms 61592 KB Output is correct
30 Correct 1834 ms 142108 KB Output is correct
31 Correct 379 ms 56476 KB Output is correct
32 Correct 332 ms 56220 KB Output is correct
33 Correct 353 ms 57884 KB Output is correct
34 Correct 383 ms 56836 KB Output is correct
35 Correct 277 ms 63132 KB Output is correct
36 Correct 41 ms 32888 KB Output is correct
37 Correct 152 ms 43696 KB Output is correct
38 Correct 325 ms 58896 KB Output is correct
39 Correct 304 ms 60572 KB Output is correct
40 Correct 429 ms 64336 KB Output is correct
41 Correct 327 ms 59164 KB Output is correct
42 Correct 377 ms 58908 KB Output is correct
43 Correct 130 ms 43864 KB Output is correct
44 Runtime error 937 ms 227084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Halted 0 ms 0 KB -