Submission #628034

#	Time	Username	Problem	Language	Result	Execution time	Memory
628034		BackNoob	Toll (BOI17_toll)	C++14	0 / 100	63 ms	29132 KiB

toll

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
const int mxN = 2e5 + 227;
const int inf = 1e9 + 7;

int n;
int m;
int q;
int k;
vector<pair<int, int>> adj[mxN];
int idx[mxN];
int lvl[mxN];

struct SegmentTree{
    struct Node{
        int f[5][5];
        int lef;
        int rig;
    };
    int n;
    vector<Node> t;
    Node base;

    SegmentTree(){}
    SegmentTree(int _n){
        n = _n;
        t.resize(n * 4 + 7);
    }

    Node mergenode(Node &x, Node &y)
    {
        if(x.lef == -1) return y;
        if(y.lef == -1) return x;
        Node res;
        res.lef = x.lef;
        res.rig = y.rig;

        // a - > b - > c -> d
        // b -> c

        for(int i = 0; i < k; i++)
        for(int j = 0; j < k; j++) res.f[i][j] = inf;

        for(int a = 0; a < k; a++)
        for(int b = 0; b < k; b++) {
            if(x.f[a][b] == inf) continue;
            for(auto it : adj[x.rig * k + b]) {
                int c = idx[it.fi];
                int cost = it.se;
                for(int d = 0; d < k; d++) {
                    if(y.f[c][d] == inf) continue;
                    res.f[a][d] = min(res.f[a][d], x.f[a][b] + cost + y.f[c][d]);
                }
            }
        }
        return res;
    }

    void build(int v, int tl, int tr)
    {
        if(tl == tr) {
            t[v].lef = t[v].rig = tl - 1;

            for(int i = 0; i < k; i++)
            for(int j = 0; j < k; j++)
                if(i == j) t[v].f[i][j] = 0;
                else t[v].f[i][j] = inf;
        }
        else {
            int tm = (tl + tr) / 2;
            build(v * 2, tl, tm);
            build(v * 2 + 1, tm + 1, tr);
            t[v] = mergenode(t[v * 2], t[v * 2 + 1]);
        }
    }

    Node query(int v, int tl, int tr, int l, int r)
    {
        if(l > r) return base;
        if(tl == l && tr == r) return t[v];
        else {
            int tm = (tl + tr) / 2;
            Node m1 = query(v * 2, tl, tm, l, min(r, tm));
            Node m2 = query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
            Node rr = mergenode(m1, m2);
            return rr;
        }
    }
    int query(int l, int r, int x, int y)
    {
        Node res = query(1, 1, n, l, r);
        return res.f[x][y];
    }
} seg;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("task.inp", "r", stdin);
    //freopen("task.out", "w", stdout);

    cin >> k >> n >> m >> q;
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }

    for(int i = 0; i < n; i++) {
        lvl[i] = i / k;
        idx[i] = i % k;
    }

    seg = SegmentTree(n / k + 7);
    seg.build(1, 1, n / k + 7);
    seg.base.lef = -1;

    while(q--) {
        int u, v;
        cin >> u >> v;
        //cout << lvl[u] << ' ' << lvl[v] << ' ' << idx[u] << ' ' << idx[v] << endl;
        int res = seg.query(lvl[u] + 1, lvl[v] + 1, idx[u], idx[v]);
        if(res == inf) cout << -1 << '\n';
        else cout << res << '\n';
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44