QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178937 | #7224. The Imaginary Girlfriend | ucup-team004 | WA | 1ms | 3684kb | C++20 | 5.0kb | 2023-09-14 15:44:42 | 2023-09-14 15:44:44 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> x1(n), y1(n), x2(n), y2(n);
std::vector<int> vx, vy;
vx.reserve(2 * n + 2);
vy.reserve(2 * n + 2);
for (int i = 0; i < n; i++) {
std::cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
vx.push_back(x1[i]);
vy.push_back(y1[i]);
vx.push_back(x2[i]);
vy.push_back(y2[i]);
}
int sx, sy, tx, ty;
std::cin >> sx >> sy >> tx >> ty;
if (sx == tx && sy == ty) {
std::cout << 0 << "\n";
return 0;
}
std::sort(vx.begin(), vx.end());
std::sort(vy.begin(), vy.end());
vx.erase(std::unique(vx.begin(), vx.end()), vx.end());
vy.erase(std::unique(vy.begin(), vy.end()), vy.end());
const int nx = vx.size();
const int ny = vy.size();
for (int i = 0; i < n; i++) {
x1[i] = std::lower_bound(vx.begin(), vx.end(), x1[i]) - vx.begin();
y1[i] = std::lower_bound(vy.begin(), vy.end(), y1[i]) - vy.begin();
x2[i] = std::lower_bound(vx.begin(), vx.end(), x2[i]) - vx.begin();
y2[i] = std::lower_bound(vy.begin(), vy.end(), y2[i]) - vy.begin();
}
sx = std::lower_bound(vx.begin(), vx.end(), sx) - vx.begin();
sy = std::lower_bound(vy.begin(), vy.end(), sy) - vy.begin();
tx = std::lower_bound(vx.begin(), vx.end(), tx) - vx.begin();
ty = std::lower_bound(vy.begin(), vy.end(), ty) - vy.begin();
std::map<std::array<int, 2>, int> id;
std::vector<std::array<int, 2>> ver;
std::vector<std::vector<int>> px(nx), py(ny);
std::vector<std::vector<std::array<int, 2>>> segx(nx), segy(ny);
for (int i = 0; i < n; i++) {
if (x1[i] == x2[i]) {
if (y1[i] > y2[i]) {
std::swap(y1[i], y2[i]);
}
segx[x1[i]].push_back({y1[i], y2[i]});
} else {
if (x1[i] > x2[i]) {
std::swap(x1[i], x2[i]);
}
segy[y1[i]].push_back({x1[i], x2[i]});
}
}
for (int x = 0; x < nx; x++) {
std::sort(segx[x].begin(), segx[x].end());
}
for (int y = 0; y < ny; y++) {
std::sort(segy[y].begin(), segy[y].end());
}
auto find = [&](auto &a, int x) {
auto it = std::lower_bound(a.begin(), a.end(), std::array{x + 1, 0});
if (it == a.begin()) {
return false;
}
it--;
return (*it)[1] >= x;
};
auto add = [&](int x, int y) {
if (id.count({x, y})) {
return;
}
if (!find(segx[x], y) && !find(segy[y], x)) {
return;
}
int u = id[{x, y}] = ver.size();
ver.push_back({x, y});
px[x].push_back(u);
py[y].push_back(u);
};
for (int i = 0; i < nx; i++) {
for (int j = 0; j < ny; j++) {
add(i, j);
}
}
const int V = ver.size();
std::vector<std::vector<std::pair<int, int>>> adj(V);
std::vector<i64> dis(V, -1);
auto addEdge = [&](int u, int v) {
int d = std::abs(vx[ver[u][0]] - vx[ver[v][0]]) + std::abs(vy[ver[u][1]] - vy[ver[v][1]]);
adj[u].emplace_back(v, d);
adj[v].emplace_back(u, d);
};
for (int x = 0; x < nx; x++) {
int m = px[x].size();
for (int i = 0, j = 0; auto [l, r] : segx[x]) {
while (i < m && ver[px[x][i]][1] < l) {
i++;
}
while (j < m && ver[px[x][j]][1] <= r) {
j++;
}
for (int k = i; k < j - 1; k++) {
int u = px[x][k];
int v = px[x][k + 1];
addEdge(u, v);
}
}
}
for (int y = 0; y < ny; y++) {
int m = py[y].size();
for (int i = 0, j = 0; auto [l, r] : segy[y]) {
while (i < m && ver[py[y][i]][0] < l) {
i++;
}
while (j < m && ver[py[y][j]][0] <= r) {
j++;
}
for (int k = i; k < j - 1; k++) {
int u = py[y][k];
int v = py[y][k + 1];
addEdge(u, v);
}
}
}
if (!id.count({sx, sy})) {
std::cout << -1 << "\n";
return 0;
}
if (!id.count({tx, ty})) {
std::cout << -1 << "\n";
return 0;
}
int S = id[{sx, sy}];
int T = id[{tx, ty}];
std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> q;
q.emplace(0, S);
while (!q.empty()) {
auto [d, x] = q.top();
q.pop();
if (dis[x] != -1) {
continue;
}
dis[x] = d;
for (auto [y, w] : adj[x]) {
q.emplace(d + w, y);
}
}
std::cout << dis[T] << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
input:
8 0 0 0 2 0 2 2 2 2 2 2 0 2 0 0 0 -1 1 1 1 1 1 1 3 1 3 -1 3 -1 1 -1 3 2 0 -1 3
output:
6
result:
ok answer is '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
10 0 0 0 3 1 0 1 3 2 0 2 3 3 0 3 3 0 0 3 0 -1 1 4 1 -1 1 -1 10000 4 1 4 10000 -1000 10000 1000 10000 0 10000 0 5000 2 3 0 5000
output:
15005
result:
ok answer is '15005'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
19 -100000 0 100000 0 -100000 0 -100000 100000 100000 0 100000 100000 -100000 100000 100000 100000 10000 0 10000 10 -10000 0 -10000 10 10000 10 -10000 10 -10000 100000 -10000 99999 -10000 99999 -10001 99999 -10001 99999 -10001 99998 -10001 99998 -10002 99998 -10002 99998 -10002 99997 -10002 99997 -1...
output:
300016
result:
wrong answer expected '300015', found '300016'