QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121883 | #5458. Shortest Path Query | 6aren | TL | 0ms | 3456kb | C++17 | 3.0kb | 2023-07-08 23:21:42 | 2023-07-08 23:21:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <cp/debugger.hpp>
#else
#define debug(...) 42
#endif
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef int64_t int64;
typedef pair<int, int> ii;
using T = int64;
struct Point {
T x;
T y;
Point(T x, T y) : x(x), y(y) {}
Point &operator+=(const Point &p) {
x += p.x, y += p.y;
return *this;
}
Point &operator-=(const Point &p) {
x -= p.x, y -= p.y;
return *this;
}
Point &operator*=(const T &v) {
x *= v, y *= v;
return *this;
}
friend Point operator-(const Point &p) { return Point(-p.x, -p.y); }
friend Point operator+(Point lhs, const Point &rhs) { return lhs += rhs; }
friend Point operator-(Point lhs, const Point &rhs) { return lhs -= rhs; }
friend Point operator*(Point lhs, const T &rhs) { return lhs *= rhs; }
};
T dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }
T cross(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }
string to_string(Point p) { return "(" + to_string(p.x) + ", " + to_string(p.y) + ")"; }
void add(vector<Point> &hull, Point p) {
while (hull.size() >= 2 && cross(hull.end()[-1] - hull.end()[-2], p - hull.end()[-1]) < 0) hull.pop_back();
hull.push_back(p);
}
vector<Point> merge(const vector<Point> &a, const vector<Point> &b) {
vector<Point> res;
int l1 = 0, l2 = 0;
while (l1 < a.size() || l2 < b.size()) {
if (l1 < a.size() && l2 < b.size()) {
if (a[l1].x < b[l2].x)
add(res, a[l1]), l1++;
else
add(res, b[l2]), l2++;
} else if (l1 < a.size()) {
add(res, a[l1]), l1++;
} else {
add(res, b[l2]), l2++;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<array<int, 2>>> g(n);
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
u--, v--;
g[v].push_back({u, c});
}
vector<vector<array<int, 3>>> queries(n);
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int a, b, x;
cin >> a >> b >> x;
x--;
queries[x].push_back({a, b, i});
}
const int D = 1024;
vector<vector<Point>> hull(D);
hull[0].push_back(Point(0, 0));
vector<int64> res(q);
for (int i = 1; i < n; i++) {
for (auto [v, c] : g[i]) {
for (auto &p : hull[v % D]) {
if (c == 0)
p.x++;
else
p.y++;
}
hull[i % D] = merge(hull[i % D], hull[v % D]);
for (auto &p : hull[v % D]) {
if (c == 0)
p.x--;
else
p.y--;
}
}
for (auto [a, b, id] : queries[i]) {
int64 ans = 1e18;
Point q(a, b);
for (auto p : hull[i % D]) {
ans = min(ans, dot(p, q));
}
res[id] = ans;
}
}
for (int i = 0; i < q; i++) {
cout << res[i] << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3456kb
input:
4 4 1 2 0 1 3 1 2 4 0 3 4 1 3 3 5 2 3 2 4 2 3 4
output:
3 4 4
result:
ok 3 number(s): "3 4 4"
Test #2:
score: -100
Memory Limit Exceeded
input:
50000 100000 1 2 1 2 3 0 3 4 1 4 5 0 5 6 1 6 7 0 7 8 1 8 9 1 9 10 0 10 11 1 11 12 1 12 13 1 13 14 0 14 15 0 15 16 0 16 17 0 17 18 1 18 19 1 19 20 0 20 21 1 21 22 0 22 23 0 23 24 1 24 25 1 25 26 0 26 27 1 27 28 0 28 29 0 29 30 0 30 31 0 31 32 1 32 33 0 33 34 1 34 35 1 35 36 1 36 37 1 37 38 0 38 39 0 ...