Submission #651336

#	Time	Username	Problem	Language	Result	Execution time	Memory
651336		dooompy	Toll (BOI17_toll)	C++17	100 / 100	880 ms	27072 KiB

toll

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct adjmat {
    ll adj[5][5];

    adjmat() {
        for (int i = 0 ; i < 5; i++){
            for (int j = 0; j < 5; j++) {
                adj[i][j] = 1e12;
            }
        }
    }
};

adjmat combine(adjmat a, adjmat b) {
        adjmat cur;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (a.adj[i][j] != 0) {
                    for (int k = 0; k < 5; k++) {
                        cur.adj[i][k] = min(cur.adj[i][k], a.adj[i][j] + b.adj[j][k]);
                    }
                }
            }
        }

        return cur;
}

struct node {
    int l, r;
    adjmat adj;

    node *lc, *rc;

    node(int _l, int _r) {
        l = _l, r = _r;

        if (l == r) return;

        int mid = (l + r) / 2;

        lc = new node(l, mid);
        rc = new node(mid + 1, r);
    }


    void upd(int group, int ql, int qr, ll cost) {
        if (l == r) {
            adj.adj[ql][qr] = min(adj.adj[ql][qr], cost);
            return;
        }

        int mid = (l + r) / 2;

        if (group <= mid) lc->upd(group, ql, qr, cost);
        else rc->upd(group, ql, qr, cost);

        adj = combine(lc->adj, rc->adj);
    }

    adjmat query(int ba, int a, int bb, int b) {
        if (ba <= l && r <= bb) return adj;
        int mid = (l + r) / 2;

        if (bb <= mid) return lc->query(ba, a, bb, b);
        if (ba > mid) return rc->query(ba, a, bb, b);
        return combine(lc->query(ba, a, bb, b), rc->query(ba, a, bb, b));
    }
};

int main() {
    int k, n, m, o; cin >> k >> n >> m >> o;

    node *root = new node(0, n);

    for (int i = 0; i < m; i++) {
        int a, b, t; cin >> a >> b >> t;
        int ga = a / k, gb = b / k;
        root->upd(ga, a % k, b % k, t);
    }

    for (int i = 0; i < o; i++) {
        int a, b; cin >> a >> b;
        if (a / k >= b/ k) {
            cout << -1 << "\n"; continue;
        }

        assert(a/k <= b/k-1);
        adjmat bruh = root->query(a / k, a % k, b / k - 1, b % k);
        cout <<( bruh.adj[a % k][b %k] >= 1e10 ? -1 : bruh.adj[a % k][b % k]) << "\n";
    }
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:83:25: warning: unused variable 'gb' [-Wunused-variable]
   83 |         int ga = a / k, gb = b / k;
      |                         ^~

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