QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#168373 | #5458. Shortest Path Query | syksykCCC | WA | 47ms | 9068kb | C++14 | 2.1kb | 2023-09-08 12:46:45 | 2023-09-08 12:46:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<pair<int, int>> vpii;
const int N = 5e4 + 5, M = 1e5 + 5, R = 1001;
vpii G[N], conv[R]; // (w = 0, w = 1)
struct query { ll u, a, b, id, ans; } Q[N];
int n, m, q;
void add(vpii &c, int x, int y) {
if(c.empty()) { c.emplace_back(x, y); return; }
if(c.back().second <= y) return;
if(c.back().first == x) y = min(c.back().second, y), c.pop_back();
while(c.size() > 1) {
int e = (int)c.size() - 1;
if((ll)(c[e-1].second - c[e].second) * (c[e].first - x)
<= (ll)(c[e].second - y) * (c[e-1].first - c[e].first)) c.pop_back();
else break;
}
c.emplace_back(x, y);
}
vpii merge(const vpii &A, const vpii &B, int dx, int dy) {
int i = 0, j = 0;
vpii res;
while(i < A.size() && j < B.size()) {
if(A[i].first <= B[i].first + dx) add(res, A[i].first, A[i].second), i++;
else add(res, B[j].first + dx, B[j].second + dy), j++;
}
for(; i < A.size(); i++) add(res, A[i].first, A[i].second);
for(; j < B.size(); j++) add(res, B[j].first + dx, B[j].second + dy);
return res;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
G[v].emplace_back(u, c); // reversed edge
}
scanf("%d", &q);
for(int i = 1; i <= q; i++) {
scanf("%lld %lld %lld", &Q[i].a, &Q[i].b, &Q[i].u);
Q[i].id = i;
}
sort(Q + 1, Q + q + 1, [&](const query &A, const query &B){ return A.u < B.u; });
conv[1].emplace_back(0, 0);
int cur = 1;
for(int u = 1; u <= n; u++) {
if(u >= R) conv[u % R].clear();
for(auto e : G[u]) {
int v = e.first, w = e.second;
conv[u % R] = merge(conv[u % R], conv[v % R], w == 0, w == 1);
}
while(cur <= q && Q[cur].u == u) {
ll ans = LLONG_MAX;
for(auto p : conv[u % R]) {
ans = min(ans, p.first * Q[cur].a + p.second * Q[cur].b);
}
Q[cur++].ans = ans;
}
}
assert(cur == q + 1);
sort(Q + 1, Q + q + 1, [&](const query &A, const query &B){ return A.id < B.id; });
for(int i = 1; i <= q; i++) printf("%lld\n", Q[i].ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4896kb
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
Wrong Answer
time: 47ms
memory: 9068kb
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:
185638090 213784513 237038034 273658506 89856130 17284446 47161678 65617298 47343432 270809489 95877614 93424311 295847953 173904741 237080454 154283163 115717250 83282228 184975675 78154972 86568645 207390557 210544104 219700223 297998155 190086169 193452259 107085328 100710713 287129781 175967742 ...
result:
wrong answer 1st numbers differ - expected: '164602050', found: '185638090'