QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#180730#5458. Shortest Path QueryrealIyxiangRE 0ms8020kbC++141.9kb2023-09-16 10:59:242023-09-16 10:59:24

Judging History

你现在查看的是测评时间为 2023-09-16 10:59:24 的历史记录

  • [2024-06-21 12:38:19]
  • 管理员手动重测本题所有提交记录
  • 测评结果:RE
  • 用时:2ms
  • 内存:8052kb
  • [2023-09-16 10:59:24]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:8020kb
  • [2023-09-16 10:59:24]
  • 提交

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
...

output:


result: