QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#168694 | #5458. Shortest Path Query | mendicillin2 | WA | 56ms | 9540kb | C++17 | 2.8kb | 2023-09-08 19:43:53 | 2023-09-08 19:43:54 |
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 = ll;
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 = 1e18;
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<ll> 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 (ll v : ans) {
cout << v << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3820kb
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: 56ms
memory: 9540kb
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: 50ms
memory: 9512kb
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 200133621 10113118 271087083 209267636 201779806 240287544 184437502 286355239 230224204 199872977 204431768 234627085 213726953 74473192 246491918 56554467 300648338 109961816 92775038 369780497 211796173 255927507 146634720 60151714 128529157 114497756 172358378 208481871 498293...
result:
wrong answer 1st numbers differ - expected: '100196045', found: '207236462'