QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291293#5458. Shortest Path Queryngpin04WA 315ms14972kbC++202.9kb2023-12-26 10:21:072023-12-26 10:21:08

Judging History

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

  • [2024-06-21 12:38:43]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:341ms
  • 内存:14968kb
  • [2023-12-26 10:21:08]
  • 评测
  • 测评结果:0
  • 用时:315ms
  • 内存:14972kb
  • [2023-12-26 10:21:07]
  • 提交

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 << i << " " << 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: 3464kb

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: 315ms
memory: 14972kb

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:

49999 2673460 59 5190 557 4250
49999 2661650 60 5190 553 4250
49999 2638970 63 5190 544 4250
49999 2509880 102 5190 466 4250
49999 2487650 110 5190 451 4250
49999 2475350 115 5190 442 4250
49999 2466360 119 5190 435 4250
49999 2451690 126 5190 423 4250
49999 2446010 129 5190 418 4250
49999 2434160 1...

result:

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