oj.uz

Submission #767893

# Submission time Handle Problem Language Result Execution time Memory
767893 2023-06-27T09:09:31 Z khshg Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 619760 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<vpi> adj;

const long long INF = 0x3f3f3f3f3f3f3f3f; // here

void Dijkstra(int st, vector<long long>& D) { // here Dis type
	int n = (int) sz(adj);
	D.resize(n, INF); // make sure to declare larger #INF# for long long
	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;
				pq.push({D[to], to});
			}
		}
	}
}

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]);
			}
		}
	}
	int tim3 = 0; trav(u, nodes) u.ss = tim3++;
	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;
	Dijkstra(nodes[mp(x[s], 0)], dis);
	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 212 KB Output is correct
2 Correct 0 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 340 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 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 300 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 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1691 ms 116016 KB Output is correct
4 Correct 1604 ms 133532 KB Output is correct
5 Correct 1222 ms 116964 KB Output is correct
6 Correct 2116 ms 104680 KB Output is correct
7 Correct 1178 ms 117152 KB Output is correct
8 Correct 2195 ms 147032 KB Output is correct
9 Correct 1380 ms 113932 KB Output is correct
10 Correct 2304 ms 180704 KB Output is correct
11 Correct 789 ms 66820 KB Output is correct
12 Correct 455 ms 55904 KB Output is correct
13 Correct 1926 ms 159436 KB Output is correct
14 Execution timed out 4067 ms 48784 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 13572 KB Output is correct
2 Execution timed out 4094 ms 619760 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 212 KB Output is correct
2 Correct 0 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 340 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 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 300 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 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1691 ms 116016 KB Output is correct
21 Correct 1604 ms 133532 KB Output is correct
22 Correct 1222 ms 116964 KB Output is correct
23 Correct 2116 ms 104680 KB Output is correct
24 Correct 1178 ms 117152 KB Output is correct
25 Correct 2195 ms 147032 KB Output is correct
26 Correct 1380 ms 113932 KB Output is correct
27 Correct 2304 ms 180704 KB Output is correct
28 Correct 789 ms 66820 KB Output is correct
29 Correct 455 ms 55904 KB Output is correct
30 Correct 1926 ms 159436 KB Output is correct
31 Execution timed out 4067 ms 48784 KB Time limit exceeded
32 Halted 0 ms 0 KB -