QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291286#5458. Shortest Path Queryngpin04WA 313ms14960kbC++202.7kb2023-12-26 10:14:422023-12-26 10:14:42

Judging History

你现在查看的是测评时间为 2023-12-26 10:14:42 的历史记录

  • [2024-06-21 12:38:36]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:358ms
  • 内存:14976kb
  • [2023-12-26 10:14:42]
  • 评测
  • 测评结果:0
  • 用时:313ms
  • 内存:14960kb
  • [2023-12-26 10:14:42]
  • 提交

answer

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define bit(n) (1LL << (n))
#define getbit(x, i) (((x) >> (i)) & 1)
#define pii pair<int, int>
#define ALL(x) x.begin(), x.end()
using namespace std;
const int M = 5e5 + 5;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e9;
const long long ooo = 1e18;
const double pi = acos(-1);

template<typename T1, typename T2> bool mini(T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("file.inp", "r",stdin);
    #endif
    int n,m;
    cin >> n >> m;
    vector <vector <pair <int, int>>> adj(n);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    
    int q; cin >> q;
    vector <vector <tuple <int, int, int>>> qr(n);
    for (int i = 0; i < q; i++) {
        int a, b, x;
        cin >> a >> b >> x;
        x--;
        qr[x].push_back({a, b, i});
    }

    const int mod = 1005;
    vector <vector <pair <int, int>>> points(1005);
    vector <int> ans(q);
    points[0].push_back({0, 0});

    auto convex = [&](vector <pair <int, int>> &p) {
        sort(ALL(p));

        vector <pair <int, int>> res;
        int sz = 0;
        for (auto [x, y] : p) {
            while (sz >= 2) {
                int a = res[sz - 1].fi - res[sz - 2].fi;
                int b = res[sz - 1].se - res[sz - 2].se;
                int u = x - res[sz - 2].fi;
                int v = y - res[sz - 2].se;
                long long prod = (long long) a * v - (long long) b * u;
                if (prod <= 0) {
                    res.pop_back();
                    sz--;
                } else 
                    break;
            }
            res.push_back({x, y});
            sz++;
        }
        p = res;
    };

    for (int i = 0; i < n; i++) {
        int j = i % mod;
        convex(points[j]);

        for (auto [a, b, ind] : qr[i]) {
            ans[ind] = 2 * oo;
            for (auto [x, y] : points[j]) 
                mini(ans[ind], x * a + y * b);
        }

        for (auto [k, w] : adj[i]) {
            int nxt = k % mod;
            for (auto [x, y] : points[j]) {
                x += (w == 0);
                y += (w == 1);
                points[nxt].push_back({x, y});
            }
        }
        points[j].clear();
    }

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

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3868kb

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: 313ms
memory: 14960kb

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:

2428440
3006051
3359191
3685769
1265210
144199
652302
427279
285665
3460010
605069
1193632
3784284
2461770
3003286
1416762
1025285
712953
2358300
564179
779640
2900491
2685828
2695331
4200075
2403401
2480233
1348588
909233
3979990
1949514
3859596
1048012
1821853
529095
2995770
1732323
3082876
381533...

result:

wrong answer 1st numbers differ - expected: '164602050', found: '2428440'