oj.uz

Submission #430643

# Submission time Handle Problem Language Result Execution time Memory
430643 2021-06-16T17:53:03 Z saleh Sky Walking (IOI19_walk) C++17
0 / 100
 196 ms 60696 KB 
#include "walk.h"
#include <bits/stdc++.h>

#define int long long
#define ft first
#define sd second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 100 * 1000 + 23, MAXV = 1000 * 1000 + 23, MAXE = 4000 * 1000 + 23, INF = 1e15;

int n, m, cnt, dis[MAXV];
vector<int> add[MAXN], del[MAXN], pt[MAXN];
set<pii> s;
map<int, int> mp[MAXN];
vector<pii> pts, g[MAXV];

void dij(int v) {/*
	for (int i = 0; i < cnt; i++) {
		cout << "\\" << i << ": " << pts[i].ft << ' ' << pts[i].sd << endl << '\t';
		for (auto j : g[i]) cout << j.ft << ' ' << j.sd << '\t';
		cout << endl;
	}*/
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, v});
	for (int i = 0; i < cnt; i++) dis[i] = INF;
	dis[v] = 0;
	while (!pq.empty()) {
		pii x = pq.top();
		pq.pop();
		if (x.ft > dis[x.sd]) continue;
		for (auto i : g[x.sd]) if (dis[i.ft] > dis[x.sd] + i.sd) {
			dis[i.ft] = dis[x.sd] + i.sd;
			pq.push({dis[i.ft], i.ft});
		}
	}
}

long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t ss, int32_t gg) {
	n = x.size();
	m = l.size();
	for (int i = 0; i < m; i++) add[l[i]].push_back(i), del[r[i]].push_back(i);
	for (int j = 0; j < n; j++) {
		for (auto i : add[j]) s.insert({y[i], i});
		pii prev = {-1, -1};
		for (auto i : s) {
			if (i.ft > h[j]) break;
			pts.push_back({i.sd, j});
			mp[i.sd][j] = cnt++;
			pt[i.sd].push_back(j);
			if (prev.sd != -1) g[cnt - 1].push_back({cnt - 2, i.ft - prev.ft}), g[cnt - 2].push_back({cnt - 1, i.ft - prev.ft});
			prev = i;
		}
		for (auto i : del[j]) s.erase({y[i], i});
	}
	for (int i = 0; i < m; i++) for (int j = 1; j < (int)pt[i].size(); j++)
		g[mp[i][pt[i][j - 1]]].push_back({mp[i][pt[i][j]], x[pt[i][j]] - x[pt[i][j - 1]]}), g[mp[i][pt[i][j]]].push_back({mp[i][pt[i][j - 1]], x[pt[i][j]] - x[pt[i][j - 1]]});
	dij(ss);
	return dis[gg];
}/*
int32_t main() { cout << min_distance({0, 4, 5, 6, 9},
{6, 6, 6, 6, 6},
{3, 1, 0},
{4, 3, 2},
{1, 3, 6},
0, 4); }*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 35532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 35516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 60696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 60696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 35532 KB Output isn't correct
2 Halted 0 ms 0 KB -