| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 938127 |
2024-03-04T20:58:29 Z |
CpDark |
OBELISK (NOI14_obelisk) |
C++17 |
|
85 ms |
33524 KB |
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 9;
long long dist1D(long long x, bool useHor, bool useVert, int m) {
if (m == 1) return x;
if (!x) return 0;
if (!useHor && !useVert) return inf;
if (!useHor) return x;
long long v = x / (m + 1);
long long sx = v * (m + 1);
if (sx == x) return 2 * v - 2;
if (!useVert) return inf;
long long fromFront = max(0LL, 2 * v - 2) + x - sx;
long long fromBack = 2 * v + (sx + m + 1) - x;
return min(fromFront, fromBack);
}
long long getDist(pair<int, int> a, pair<int, int> b, int m) {
int x = abs(a.first - b.first), y = abs(a.second - b.second);
long long ans = inf;
for (int useVert = 0; useVert < 2; ++useVert) {
for (int useHor = 0; useHor < 2; ++useHor) {
ans = min(ans, 2 * (useHor + useVert) + dist1D(x, useHor, useVert, m) + dist1D(y, useVert, useHor, m));
}
}
return ans;
}
vector<vector<pair<int, long long>>> graph;
vector<long long> dist;
void dijkstra(int root, int n) {
dist.resize(n, inf);
vector<bool> done(n, false);
priority_queue<pair<int, long long>, vector<pair<int, long long>>, greater<pair<int, long long>>> pq;
dist[root] = 0;
pq.push({ 0,root });
while (!pq.empty()) {
int v = pq.top().second;
pq.pop();
if (done[v]) continue;
done[v] = true;
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
long long w = graph[v][i].second;
if (dist[u] > dist[v] + w) {
dist[u] = dist[v] + w;
pq.push({ dist[u],u });
}
}
}
}
long long solve(int n, int m, pair<int, int> s, pair<int, int>e, vector<vector<pair<int, int>>> holes) {
int counter = 0;
for (int i = 0;i < holes.size();i++) counter += holes[i].size();
vector<vector<int>> id(holes.size());
graph.resize(counter + 2);
// build graph
int index = 1;
for (int i = 0;i < holes.size();i++) {
id[i].resize(holes[i].size());
for (int j = 0;j < holes[i].size();j++) {
id[i][j] = index++;
// if last level connect to end point
if (i == holes.size() - 1) graph[id[i][j]].push_back({ counter + 1,getDist(holes[i][j],e, m) });
// if first level connect start point
if (i == 0) {
graph[0].push_back({ id[i][j], getDist(s,holes[i][j], m) });
continue;
}
// connect this level to previous level
for (int k = 0;k < holes[i - 1].size();k++) {
graph[id[i - 1][k]].push_back({ id[i][j], getDist(holes[i - 1][k], holes[i][j], m) });
}
}
}
dijkstra(0, index + 1);
return dist[index];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, K;
pair<int, int> S, E;
cin >> N >> M >> S.first >> S.second >> E.first >> E.second;
vector<vector<pair<int, int>>> H(N - 1);
for (int i = 0;i < N - 1;i++) {
cin >> K;
H[i].resize(K);
for (int j = 0;j < K;j++) cin >> H[i][j].first >> H[i][j].second;
}
cout << solve(N, M, S, E, H);
return 0;
}
Compilation message
obelisk.cpp: In function 'void dijkstra(int, int)':
obelisk.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
obelisk.cpp: In function 'long long int solve(int, int, std::pair<int, int>, std::pair<int, int>, std::vector<std::vector<std::pair<int, int> > >)':
obelisk.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0;i < holes.size();i++) counter += holes[i].size();
| ~~^~~~~~~~~~~~~~
obelisk.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0;i < holes.size();i++) {
| ~~^~~~~~~~~~~~~~
obelisk.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int j = 0;j < holes[i].size();j++) {
| ~~^~~~~~~~~~~~~~~~~
obelisk.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if (i == holes.size() - 1) graph[id[i][j]].push_back({ counter + 1,getDist(holes[i][j],e, m) });
| ~~^~~~~~~~~~~~~~~~~~~
obelisk.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int k = 0;k < holes[i - 1].size();k++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
75 ms |
32040 KB |
Output is correct |
| 3 |
Correct |
73 ms |
30548 KB |
Output is correct |
| 4 |
Correct |
73 ms |
31428 KB |
Output is correct |
| 5 |
Correct |
78 ms |
32852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
30796 KB |
Output is correct |
| 2 |
Correct |
75 ms |
29400 KB |
Output is correct |
| 3 |
Correct |
72 ms |
30240 KB |
Output is correct |
| 4 |
Correct |
85 ms |
33524 KB |
Output is correct |
| 5 |
Correct |
71 ms |
31096 KB |
Output is correct |
