QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291268#5458. Shortest Path Queryngpin04TL 0ms3524kbC++143.3kb2023-12-26 09:47:152024-06-21 12:38:32

Judging History

你现在查看的是最新测评结果

  • [2024-06-21 12:38:32]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:0ms
  • 内存:3524kb
  • [2023-12-26 09:47:16]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3536kb
  • [2023-12-26 09:47:15]
  • 提交

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);
    map <pair <int, int>, int> edges;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (getbit(edges[mp(u, v)], w))
            continue;
        edges[{u, v}] |= bit(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) {

        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--;
                }
            }
            res.push_back({x, y});
        }
        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;
            vector <pair <int, int>> newp;
            for (auto [x, y] : points[j]) {
                x += (w == 0);
                y += (w == 1);
                // points[nxt].push_back({x, y});
                newp.push_back({x, y});
            }

            vector <pair <int, int>> newnxt;
            for (int i = 0, j = 0; i < (int) points[nxt].size() || j < (int) newp.size();) {
                if (i == points[nxt].size() || (j < (int) newp.size() && newp[j] < points[nxt][i]))
                    newnxt.push_back(newp[j++]);
                else
                    newnxt.push_back(points[nxt][i++]);
            }
            points[nxt] = newnxt;
            convex(points[nxt]);
        }
        points[j].clear();
    }
    
    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";
    return 0;
}

详细

Test #1:

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

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
Time Limit Exceeded

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: