QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75819 | #5458. Shortest Path Query | XKError | WA | 56ms | 10104kb | C++14 | 2.0kb | 2023-02-06 12:00:44 | 2023-02-06 12:00:46 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 50005
#define ll long long
using namespace std;
int n, m, Q;
struct node{
int x, y;
node operator +(node b) {
return {x + b.x, y + b.y};
}
node operator -(node b) {
return {x - b.x, y - b.y};
}
ll operator *(node b) {
return 1ll * x * b.y - 1ll * y * b.x;
}
};
int tot;
node tmp[maxn];
int top;
node stk[maxn];
vector<node> cv[maxn];
vector<pair<int, int> > g[maxn];
struct qR{
int a, b, id;
};
vector<qR> q[maxn];
ll ans[maxn];
void conv(vector<node> &a, vector<node> &b) {
int ia = 0, ib = 0;
tot = 0;
while (ia < (int)a.size() && ib < (int)b.size()) {
if ((a[ia].x == b[ib].x && a[ia].y < b[ib].y) || a[ia].x < b[ib].x) tmp[++tot] = a[ia++];
else tmp[++tot] = b[ib++];
}
while (ia < (int)a.size()) tmp[++tot] = a[ia++];
while (ib < (int)b.size()) tmp[++tot] = b[ib++];
a.clear();
top = 0;
for (int i = 1; i <= tot; i++) {
if (top > 1 && (stk[top] - stk[top - 1]) * (tmp[i] - stk[top]) >= 0) --top;
stk[++top] = tmp[i];
}
for (int i = 1; i <= top; i++) a.push_back(stk[i]);
}
int main() {
memset(ans, 0x3f, sizeof ans);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
g[y].push_back({x, z});
}
scanf("%d", &Q);
for (int i = 1; i <= Q; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
q[z].push_back({x, y, i});
}
cv[1].push_back({0, 0});
for (int i = 2; i <= n; i++) {
if (i - 1002 > 0) {
vector<node>().swap(cv[i - 1002]);
}
for (auto p : g[i]) {
auto tmp = cv[p.first];
for (auto &x : tmp) {
if (p.second == 0) ++x.x;
else ++x.y;
}
conv(cv[i], tmp);
}
// for (auto x : cv[i]) {
// cout<<x.x<<","<<x.y<<" ";
// }
// puts("");
for (auto p : q[i]) {
for (auto x : cv[i]) {
ans[p.id] = min(ans[p.id], 1ll * p.a * x.x + 1ll * p.b * x.y);
}
}
}
for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7584kb
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: 56ms
memory: 10104kb
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:
171090050 250459598 258589143 259699419 104338880 16685198 59196446 64713954 46949896 245672377 94777502 84753103 267419449 192242757 216482422 147454419 111021650 80187604 247374700 111782626 121405290 249524638 191332392 202049239 343798460 173714177 174899498 97998224 96431009 280559577 164349486...
result:
wrong answer 1st numbers differ - expected: '164602050', found: '171090050'