oj.uz

Submission #831156

# Submission time Handle Problem Language Result Execution time Memory
831156 2023-08-19T19:52:18 Z PurpleCrayon Sky Walking (IOI19_walk) C++17
10 / 100
 30 ms 17000 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10;
const ll INF = 1e18+10;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

int n, m;
vector<pair<int, int>> adj[N];
ll dist[N];

void add_edge(int a, int b, int w) {
    assert(w >= 0);
	adj[a].emplace_back(b, w);
	adj[b].emplace_back(a, w);
}

void dijkstra(int S) {
	fill(dist, dist + N, INF);

	min_pq<pair<ll, int>> pq;
	pq.push({dist[S] = 0, S});

	while (!pq.empty()) {
		auto [d_c, c] = pq.top(); pq.pop();
		if (dist[c] != d_c) continue;
		for (auto [nxt, w] : adj[c]) {
			if (dist[nxt] > dist[c] + w) {
				dist[nxt] = dist[c] + w;
				pq.push({dist[nxt], nxt});
			}
		}
	}
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = sz(x), m = sz(l);
    for (int i = 0; i < m; i++) {
        for (int j = l[i]; j <= r[i]; j++) {
            // i * n + j
            if (j > l[i]) {
                add_edge(i * n + j - 1, i * n + j, x[j] - x[j-1]);
            }
        }
    }

    for (int j = 0; j < n; j++) {
        vector<int> open;
        for (int i = 0; i < m; i++) if (l[i] <= j && j <= r[i] && y[i] <= h[j]) {
            open.push_back(i);
        }
        sort(open.begin(), open.end(), [&](int a, int b) { return y[a] < y[b]; });

        int p = -1;
        for (int i : open) {
            if (p != -1) {
                add_edge(i * n + j, p * n + j, y[i] - y[p]);
            }

            p = i;
        }
    }

    int S = n * m;
    for (int i = 0; i < m; i++) {
        if (l[i] <= s && s <= r[i] && y[i] <= h[s]) {
            add_edge(S, i * n + s, y[i]);
        }
    }

    dijkstra(S);

    ll ans = INF;
    for (int i = 0; i < m; i++) {
        if (l[i] <= g && g <= r[i] && y[i] <= h[g]) {
            ans = min(ans, dist[i * n + g] + y[i]);
        }
    }

    return (ans == INF ? -1 : ans);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6536 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6544 KB Output is correct
7 Correct 3 ms 6540 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 3 ms 6540 KB Output is correct
12 Correct 3 ms 6484 KB Output is correct
13 Correct 3 ms 6484 KB Output is correct
14 Correct 3 ms 6484 KB Output is correct
15 Correct 3 ms 6540 KB Output is correct
16 Correct 3 ms 6536 KB Output is correct
17 Correct 3 ms 6612 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6540 KB Output is correct
3 Runtime error 30 ms 17000 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 13280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 13280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6536 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6544 KB Output is correct
7 Correct 3 ms 6540 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 3 ms 6612 KB Output is correct
11 Correct 3 ms 6540 KB Output is correct
12 Correct 3 ms 6484 KB Output is correct
13 Correct 3 ms 6484 KB Output is correct
14 Correct 3 ms 6484 KB Output is correct
15 Correct 3 ms 6540 KB Output is correct
16 Correct 3 ms 6536 KB Output is correct
17 Correct 3 ms 6612 KB Output is correct
18 Correct 3 ms 6484 KB Output is correct
19 Correct 3 ms 6540 KB Output is correct
20 Runtime error 30 ms 17000 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -