oj.uz

Submission #767886

# Submission time Handle Problem Language Result Execution time Memory
767886 2023-06-27T09:05:26 Z khshg Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 643300 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define ff first
#define ss second
 
#define ar array
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
 
#define sz(x) (int)((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define trav(a, x) for(auto& a : x)
 
template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); }

V<vpl> adj;

const long long INF = 0x3f3f3f3f3f3f3f3f; // here

void Dijkstra(int st, vector<long long>& D, vector<int>& P) { // here Dis type
	int n = (int) sz(adj);
	D.resize(n, INF); // make sure to declare larger #INF# for long long
	P.resize(n, -1);
	using tp = pair<long long, int>; // here
	priority_queue<tp, vector<tp>, greater<tp>> pq;
	pq.push({0, st});
	D[st] = 0;
	while(!pq.empty()) {
		long long D_to_cur = pq.top().first; // here
		int cur = pq.top().second;
		pq.pop();
		if(D_to_cur != D[cur]) {
			continue;
		}
		for(auto& u : adj[cur]) {
			int to = u.first;
			long long len = u.second; // here
			if(D[cur] + len < D[to]) {
				D[to] = D[cur] + len;
				P[to] = cur;
				pq.push({D[to], to});
			}
		}
	}
}

vector<int> Restore_Path(int st, int en, vector<int>& P) {
	vector<int> path;
	while(en != st) {
		path.push_back(en);
		en = P[en];
	}
	path.push_back(st);
	reverse(begin(path), end(path));
	return path;
}

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 = sz(x);
	V<vi> up(N, vi{0});
	map<pi, int> nodes;
	F0R(i, N) nodes[mp(x[i], 0)];
	int M = sz(l);
	F0R(i, M) {
		FOR(cur, l[i], r[i] + 1) {
			if(h[cur] >= y[i]) {
				nodes[mp(x[cur], y[i])];
				up[cur].pb(y[i]);
			}
		}
	}
	vpi inv;
	{
		int tim3 = 0; trav(u, nodes) u.ss = tim3++;
		inv.rsz(tim3);
		trav(u, nodes) {
			inv[u.ss] = u.ff;
		}
	}
	adj.rsz(sz(nodes));
	F0R(i, N) {
		sor(up[i]);
		up[i].erase(unique(all(up[i])), end(up[i]));
		F0R(j, sz(up[i]) - 1) {
			adj[nodes[mp(x[i], up[i][j])]].eb(nodes[mp(x[i], up[i][j + 1])], up[i][j + 1] - up[i][j]);
			adj[nodes[mp(x[i], up[i][j + 1])]].eb(nodes[mp(x[i], up[i][j])], up[i][j + 1] - up[i][j]);
		}
	}
	F0R(i, M) {
		pi prev = {-1, -1};
		FOR(cur, l[i], r[i] + 1) {
			if(h[cur] >= y[i]) {
				if(prev != mp(-1, -1)) {
					adj[nodes[prev]].eb(nodes[mp(x[cur], y[i])], x[cur] - prev.ff);
					adj[nodes[mp(x[cur], y[i])]].eb(nodes[prev], x[cur] - prev.ff);
				}
				prev = mp(x[cur], y[i]);
			}
		}
	}
	vl dis;
	vi path;
	Dijkstra(nodes[mp(x[s], 0)], dis, path);
	if(dis[nodes[mp(x[g], 0)]] == INF) return -1;
	return dis[nodes[mp(x[g], 0)]];
}/*

int main() {
	int n, m;
	assert(2 == scanf("%d%d", &n, &m));
	vector<int> x(n), h(n);
	for (int i = 0; i < n; i++)
		assert(2 == scanf("%d%d", &x[i], &h[i]));
	vector<int> l(m), r(m), y(m);
	for (int i = 0; i < m; i++)
		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
	int s, g;
	assert(2 == scanf("%d%d", &s, &g));
	fclose(stdin);

	long long result = min_distance(x, h, l, r, y, s, g);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 448 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1835 ms 148296 KB Output is correct
4 Correct 1661 ms 166864 KB Output is correct
5 Correct 1401 ms 144564 KB Output is correct
6 Correct 2157 ms 128732 KB Output is correct
7 Correct 1285 ms 144712 KB Output is correct
8 Correct 2313 ms 188260 KB Output is correct
9 Correct 1431 ms 141976 KB Output is correct
10 Correct 2504 ms 227380 KB Output is correct
11 Correct 845 ms 83240 KB Output is correct
12 Correct 465 ms 64076 KB Output is correct
13 Correct 2062 ms 201184 KB Output is correct
14 Execution timed out 4051 ms 54040 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 16540 KB Output is correct
2 Execution timed out 4094 ms 643300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 16540 KB Output is correct
2 Execution timed out 4094 ms 643300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 448 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1835 ms 148296 KB Output is correct
21 Correct 1661 ms 166864 KB Output is correct
22 Correct 1401 ms 144564 KB Output is correct
23 Correct 2157 ms 128732 KB Output is correct
24 Correct 1285 ms 144712 KB Output is correct
25 Correct 2313 ms 188260 KB Output is correct
26 Correct 1431 ms 141976 KB Output is correct
27 Correct 2504 ms 227380 KB Output is correct
28 Correct 845 ms 83240 KB Output is correct
29 Correct 465 ms 64076 KB Output is correct
30 Correct 2062 ms 201184 KB Output is correct
31 Execution timed out 4051 ms 54040 KB Time limit exceeded
32 Halted 0 ms 0 KB -