QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#168693 | #5458. Shortest Path Query | mendicillin2 | WA | 80ms | 9144kb | C++17 | 2.8kb | 2023-09-08 19:43:01 | 2023-09-08 19:43:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using ll = int64_t;
using vi = vc<int>;
template <class F>
struct ycr {
F f;
template <class T>
explicit ycr(T&& f_) : f(forward<T>(f_)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return f(ref(*this), forward<Args>(args)...);
}
};
template <class F>
decltype(auto) yc(F&& f) {
return ycr<decay_t<F>>(forward<F>(f));
}
using D = int;
int sgn(D a) {
return (a > 0) - (a < 0);
}
struct P {
D x, y;
P(D x_ = 0, D y_ = 0) : x(x_), y(y_) {}
P operator + (const P& o) const { return P(x + o.x, y + o.y); }
P operator - (const P& o) const { return P(x - o.x, y - o.y); }
};
D cross(const P& a, const P& b) {
return a.x * b.y - a.y * b.x;
}
D cross(const P& a, const P& b, const P& c) {
return cross(b - a, c - a);
}
vc<P> lower_hull(vc<P> pts) {
int n = sz(pts);
sort(pts.begin(), pts.end(), [&](const P& a, const P& b) -> bool {
return tie(a.x, a.y) < tie(b.x, b.y);
});
vc<P> res;
for (int i = 0; i < n; res.push_back(pts[i++])) {
for (; res.size() > 1 && sgn(cross(res.end()[-2], res.end()[-1], pts[i])) <= 0; res.pop_back()) {}
}
return res;
}
#define LOCAL true
#if LOCAL
constexpr int L = 3;
#else
constexpr int L = 1010;
#endif
const ll INF = 1e9;
template <class T> void setmin(T& a, const T& b) {
if (a > b) a = b;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
int N, M; cin >> N >> M;
struct edge_t {
int b, c;
};
vector<edge_t> edges(M);
vector<vector<int>> adj(N);
for (int e = 0; e < M; e++) {
int u, v, c; cin >> u >> v >> c; u--, v--;
assert(u < v);
edges[e] = {v, c};
adj[u].push_back(e);
}
int Q; cin >> Q;
struct query_t {
int a, b;
};
vector<query_t> queries(Q);
vector<vector<int>> queries_at(N);
for (int q = 0; q < Q; q++) {
int a, b, x; cin >> a >> b >> x; x--;
queries[q] = {a, b};
queries_at[x].push_back(q);
}
vector<int> ans(Q, INF);
vector<vector<P>> dp(L);
dp[0].emplace_back(0, 0);
for (int x = 0; x < N; x++) {
auto& cnds = dp[x % L];
cnds = lower_hull(cnds);
for (int q : queries_at[x]) {
const auto& [a, b] = queries[q];
for (const auto& pt : cnds) {
setmin(ans[q], a * pt.x + b * pt.y);
}
}
for (int e : adj[x]) {
const auto& [y, c] = edges[e];
const int dx = (c == 0 ? 1 : 0);
const int dy = (c == 0 ? 0 : 1);
auto& tgt = dp[y % L];
for (const auto& pt : cnds) {
tgt.emplace_back(pt.x + dx, pt.y + dy);
}
}
cnds.clear();
}
for (int v : ans) {
cout << v << '\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
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: 0
Accepted
time: 70ms
memory: 9112kb
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 ...
output:
164602050 208733870 228180204 248456409 87574800 16685198 46684062 64713954 46949896 240633535 94777502 83016099 259833741 167838804 214963500 147454419 111021650 80187604 184782450 78138570 86528820 203553394 188095596 202049239 290053220 172790198 168899028 97757186 96431009 266952297 164349486 26...
result:
ok 50000 numbers
Test #3:
score: -100
Wrong Answer
time: 80ms
memory: 9144kb
input:
50000 100000 1 2 1 2 3 0 3 4 1 4 5 0 5 6 0 6 7 1 7 8 0 8 9 0 9 10 1 10 11 1 11 12 1 12 13 1 13 14 0 14 15 1 15 16 1 16 17 1 17 18 0 18 19 0 19 20 1 20 21 1 21 22 1 22 23 0 23 24 0 24 25 1 25 26 1 26 27 0 27 28 0 28 29 1 29 30 0 30 31 1 31 32 1 32 33 1 33 34 0 34 35 1 35 36 1 36 37 1 37 38 0 38 39 0 ...
output:
207236462 64935253 -2013314627 10113118 271087083 209267636 -2143426405 240287544 184437502 -2009848075 -1885814346 -216854452 204431768 234627085 -273364603 -1490026777 246491918 56554467 300648338 -1562891983 92775038 -362788086 211796173 -1939023004 -587123726 -932084455 128529157 -80697416 -1960...
result:
wrong answer 1st numbers differ - expected: '100196045', found: '207236462'