QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75499#5458. Shortest Path QueryJooDdaeRE 2ms7132kbC++171.6kb2023-02-05 14:43:502023-02-05 14:43:54

Judging History

你现在查看的是测评时间为 2023-02-05 14:43:54 的历史记录

  • [2024-06-21 12:37:17]
  • 管理员手动重测本题所有提交记录
  • 测评结果:RE
  • 用时:1ms
  • 内存:7360kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 14:43:54]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:7132kb
  • [2023-02-05 14:43:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, q, ans[50050];
vector<array<int, 2>> v[50050], c[50050];
vector<array<int, 3>> Q[50050];


int find(int x) {
    int re = 1;
    while((re+1)*(re+1)*(re+1) <= x) re++;
    return re*re;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int a, b, c; cin >> a >> b >> c;
        v[b].push_back({a, c});
    }
    cin >> q;
    for(int i=1;i<=q;i++) {
        int a, b, c; cin >> a >> b >> c;
        Q[c].push_back({a, b, i});
    }

    c[1].push_back({0, 0});
    for(int i=1;i<=n;i++) {
        for(auto [x, y] : v[i]) {
            vector<array<int, 2>> C;

            int j = 0, k = 0;
            while(j < c[i].size() || k < c[x].size()) {
                int X = 0, Y = 0;
                if(k == c[x].size() || (j < c[i].size() && (c[i][j][0] > c[x][k][0]+!y || (c[i][j][0] == c[x][k][0]+!y && c[i][j][1] > c[x][k][1]+y)))) {
                    X = c[i][j][0], Y = c[i][j][1], j++;
                } else {
                    X = c[x][k][0]+!y, Y = c[x][k][1]+y, k++;
                }
                while(!C.empty() && C.back()[1] >= Y) C.pop_back();
                C.push_back({X, Y});
            }

            swap(c[i], C);
        }
        int k = pow(i, 2./3);
        assert(c[i].size() <= max(1, k));

        for(auto [a, b, id] : Q[i]) {
            ans[id] = INT_MAX;
            for(auto [x, y] : c[i]) ans[id] = min(ans[id], a*x + b*y);
        }

        if(i > 1000) c[i-1000].clear();
    }

    for(int i=1;i<=q;i++) cout << ans[i] << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 7132kb

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
Dangerous Syscalls

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: