QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180730 | #5458. Shortest Path Query | realIyxiang | RE | 0ms | 8020kb | C++14 | 1.9kb | 2023-09-16 10:59:24 | 2023-09-16 10:59:24 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 5e4 + 5, M = 1500 + 5, K = 1e3 + 1;
struct edge { int u, c; } ;
struct qry { int a, b, id; } ;
struct node { int x, y; } A[M], st[M], f[M][M];
int n, m, u, v, c, q, a, b, x, tp, res, cnt[N], ans[N];
vector <edge> G[N];
vector <qry> Q[N];
double slope (node a, node b) {
return 1.0 * (a.y - b.y) / (a.x - b.x);
}
void insert (node p) {
for ( ; tp > 1 && slope(st[tp - 1], st[tp]) > slope(st[tp - 1], p); --tp) ;
st[++tp] = p;
}
void Merge (int &c1, node *A, int c2, node *B) {
int i = 1, j = 1; tp = 0;
for ( ; i <= c1 && j <= c2; ) {
if(A[i].x == B[j].x) insert((node){A[i].x, min(A[i].y, B[j].y)}), ++i, ++j;
else if(A[i].x < B[j].x) insert(A[i]), ++i;
else insert(B[j]), ++j;
}
for ( ; i <= c1; ++i) insert(A[i]);
for ( ; j <= c2; ++j) insert(B[j]);
c1 = tp;
rep(i, 1, c1) A[i] = st[i];
}
int main () {
ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
rep(i, 1, m) cin >> u >> v >> c, G[v].push_back((edge){u, c});
cin >> q;
rep(i, 1, q) cin >> a >> b >> x, Q[x].push_back((qry){a, b, i});
f[1][cnt[1] = 1] = (node){0, 0};
rep(i, 2, n) {
int u = i % K; cnt[u] = 0;
for (auto e : G[i]) {
res = cnt[e.u % K];
rep(j, 1, res) {
A[j] = f[e.u % K][j];
A[j].x += (!e.c), A[j].y += (e.c);
}
Merge(cnt[u], f[u], res, A);
}
sort(Q[i].begin(), Q[i].end(), [](qry a, qry b) {
return -1.0 * a.a / a.b < -1.0 * b.a / b.b;
});
for (int j = 0, k = 1; j < Q[i].size(); ++j) {
for ( ; k < cnt[u] && slope(f[u][k], f[u][k + 1]) < -1.0 * Q[i][j].a / Q[i][j].b; ++k) ;
ans[Q[i][j].id] = Q[i][j].a * f[u][k].x + Q[i][j].b * f[u][k].y;
}
}
rep(i, 1, q) cout << ans[i] << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8020kb
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
Runtime Error
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 ...