QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291292#5458. Shortest Path Queryngpin04WA 312ms14964kbC++202.9kb2023-12-26 10:20:312023-12-26 10:20:32

Judging History

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

  • [2024-06-21 12:38:43]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:357ms
  • 内存:14952kb
  • [2023-12-26 10:20:32]
  • 评测
  • 测评结果:0
  • 用时:312ms
  • 内存:14964kb
  • [2023-12-26 10:20:31]
  • 提交

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;
        assert(v - u <= 1000);
        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]) 
                if (mini(ans[ind], x * a + y * b) && n >= 100 && ind == 0)
                    cout << ans[ind] << " " << x << " " << a << " " << y << " " << b << "\n";
        }

        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: 1ms
memory: 3628kb

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: 312ms
memory: 14964kb

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:

2673460 59 5190 557 4250
2661650 60 5190 553 4250
2638970 63 5190 544 4250
2509880 102 5190 466 4250
2487650 110 5190 451 4250
2475350 115 5190 442 4250
2466360 119 5190 435 4250
2451690 126 5190 423 4250
2446010 129 5190 418 4250
2434160 139 5190 403 4250
2430360 144 5190 396 4250
2428930 147 5190 ...

result:

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