oj.uz

Submission #1048885

# Submission time Handle Problem Language Result Execution time Memory
1048885 2024-08-08T10:19:49 Z fuad27 Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 454572 KB 
#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
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 st, int ed) {
#define int long long
	int n = h.size();
	int m = y.size();
	vector<int> bl;
	vector<int> br(m);
	bl.resize(n);
	iota(bl.begin(),bl.end(), 0);
	iota(br.begin(),br.end(), 0);
	sort(bl.begin(), bl.end(), [&](int u, int v) -> bool {
		return h[u] > h[v];
	});
	sort(br.begin(), br.end(), [&](int u, int v) -> bool {
		return y[u] > y[v];
	});
	int p1 = 0;
	set<int> s;
	map<int,vector<int>> mp;
	map<int,vector<int>> coords;



	vector<vector<pair<int,long long>>> g;
	
	map<pair<int,int>, int> cmp;
	auto add = [&](int x, int y) -> int {
		if(cmp.find(pair<int,int>(x, y))!=cmp.end())return cmp[{x, y}];
		cmp[{x,y}]=g.size();
		coords[x].push_back(y);
		g.push_back({});
		return cmp[{x,y}];
	};
	for(int i = 0;i<m;i++) {
		while(p1 < n and h[bl[p1]] >= y[br[i]]) {
			mp[x[bl[p1]]].push_back(bl[p1]);
			s.insert(x[bl[p1++]]);	
		}
		int prev=-1;
		for(auto it = s.lower_bound(x[l[br[i]]]);it!=s.end();it++) {
			if((*it) > x[r[br[i]]])break;
			int at = (*it);
//			cout << y[br[i]] << " " << at << endl;
			if(coords[at].size())
			coords[at].push_back(y[br[i]]);
			else coords[at].push_back(0);
			add(at, y[br[i]]);
			add(at, 0);
			if(prev!=-1) {
				g[add(prev, y[br[i]])].push_back({add(at, y[br[i]]), abs(at-prev)});
				g[add(at, y[br[i]])].push_back({add(prev, y[br[i]]), abs(at-prev)});
			}
			prev=at;
		}
	}
	for(auto &i:coords) {
		sort(i.second.begin(), i.second.end());
		for(int j = 1;j<(int)(i.second).size();j++) {
//			cout << i.first << " " << i.second[j-1] << " " << i.second[j] << endl;
//			cout << i.first << " " <<  i.second[j-1] << " " << i.second[j] << endl;
			g[add(i.first, i.second[j-1])].push_back({add(i.first, i.second[j]), abs(i.second[j]-i.second[j-1])});
			g[add(i.first, i.second[j])].push_back({add(i.first, i.second[j-1]), abs(i.second[j]-i.second[j-1])});
		}
	}
//	cout << endl;
	priority_queue<pair<long long,int>> pq;
	pq.push(pair<long long, int>(0ll, add(x[st], 0)));
	vector<long long> dist(g.size(), (long long)2e18);
	dist[add(x[st], 0)] = 0;

	map<int, pair<int,int>> revs;
	for(auto i:cmp) {
		revs[i.second] = i.first;
	}
	while(pq.size()) {
		int at = pq.top().second;
//		cout << revs[at].first << " " << revs[at].second << " " << dist[at] << endl;
		pq.pop();
		for(auto [to, w]:g[at]){ 
			if(dist[to] > dist[at] + w) {
				dist[to] = dist[at]+w;
				pq.push(pair<long long, int> (-dist[to], to));
			}
		}
	}
	return dist[add(x[ed], 0)];
#undef int
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2068 ms 257260 KB Output is correct
4 Correct 2345 ms 293608 KB Output is correct
5 Correct 1690 ms 257000 KB Output is correct
6 Correct 1534 ms 229356 KB Output is correct
7 Incorrect 1658 ms 257232 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 28416 KB Output is correct
2 Execution timed out 4098 ms 454572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 28416 KB Output is correct
2 Execution timed out 4098 ms 454572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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