oj.uz

Submission #825789

# Submission time Handle Problem Language Result Execution time Memory
825789 2023-08-15T08:05:58 Z tomruk Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 600504 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
map<int,vector<int>> adj[N];
map<int,int> d[N];
long long min_distance(vector<int> p, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = p.size();
	int m = l.size();
	vector<pair<int,int>> v;
	for(int i = 0;i<n;i++){
		v.push_back({h[i],i});
		adj[i][0];
	}
	for(int i = 0;i<m;i++){
		v.push_back({y[i],~i});
	}
	sort(v.rbegin(),v.rend());
	set<int> active;
	for(auto u:v){
		if(u.second < 0){
			u.second = ~u.second;
			auto it = active.lower_bound(l[u.second]);
			while(1){
				auto it2 = it;
				it2++;
				if(it2 == active.end() || *it2 > r[u.second])
					break;
				adj[*it][y[u.second]].push_back(*it2);
				adj[*it2][y[u.second]].push_back(*it);
				it = it2;
			}
		}
		else{
			active.insert(u.second);
		}
	}
	priority_queue<pair<long long,pair<int,int>>> q;
	d[s][0] = 0;
	q.push({-d[s][0],{s,0}});
	while(q.size()){
		auto tp = q.top();
		q.pop();
		tp.first *= -1;
		int x = tp.second.first;
		int y = tp.second.second;
		if(tp.first != d[x][y])
			continue;
		// cout << x << ' ' << y << endl;
		// cout << tp.first << endl;
		for(auto u:adj[x][y]){
			long long nw = abs(p[x] - p[u]) + tp.first;
			if(d[u].count(y) == 0 || d[u][y] > nw){
				d[u][y] = nw;
				q.push({-d[u][y],{u,y}});
			}
		}
		auto it = adj[x].find(y);
		if(next(it) != adj[x].end()){
			long long nw = abs(y - next(it)->first) + tp.first;
			if(d[x].count(next(it)->first) == 0 || d[x][next(it)->first] > nw){
				d[x][next(it)->first] = nw;
				q.push({-d[x][next(it)->first],{x,next(it)->first}});
			}
		}
		if(it != adj[x].begin()){
			long long nw = abs(y - prev(it)->first) + tp.first;
			if(d[x].count(prev(it)->first) == 0 || d[x][prev(it)->first] > nw){
				d[x][prev(it)->first] = nw;
				q.push({-d[x][prev(it)->first],{x,prev(it)->first}});
			}
		}
	}
	return (d[g].count(0)?d[g][0]:-1);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9640 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9696 KB Output is correct
5 Correct 6 ms 9692 KB Output is correct
6 Correct 5 ms 9700 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Incorrect 5 ms 9700 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Incorrect 1961 ms 126440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 23236 KB Output is correct
2 Execution timed out 4067 ms 600504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 23236 KB Output is correct
2 Execution timed out 4067 ms 600504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9640 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9696 KB Output is correct
5 Correct 6 ms 9692 KB Output is correct
6 Correct 5 ms 9700 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Incorrect 5 ms 9700 KB Output isn't correct
10 Halted 0 ms 0 KB -