Submission #1268427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268427		ducdev	Toll (BOI17_toll)	C++17	100 / 100	128 ms	93748 KiB

toll

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int MAX_N = 5e4;
const int MOD = 1e9 + 7;
const int INF = 1e9;

template <class X, class Y>
bool minimize(X &x, const Y &y) {
    if (x <= y) return false;
    x = y;
    return true;
};

int n, q, m, k;
vector<ii> queries;
vector<ii> adj[MAX_N + 5];

namespace SUBTASK_1 {
    const int N = MAX_N;
    const int K = 1;

    int numChains;
    int lab[N + 5];
    ll pref[N + 5];

    void dfs(int u) {
        lab[u] = numChains;

        for (ii e : adj[u]) {
            int v = e.first, w = e.second;
            pref[v] = pref[u] + w;
            dfs(v);
        };
    };

    void Solve() {
        for (int u = 0; u < n; u++) {
            if (!lab[u]) {
                ++numChains;
                dfs(u);
            };
        };

        for (const ii &q : queries) {
            int u = q.first, v = q.second;
            if (lab[u] != lab[v]) {
                cout << -1 << '\n';
            } else {
                cout << pref[v] - pref[u] << '\n';
            };
        };
    };
};  // namespace SUBTASK_1

namespace SUBTASK_234 {
    const int N = MAX_N;

    int ans[N + 5], dist[N + 5];
    bool inQueue[N + 5];
    vector<ii> qu[N + 5];

    bool checkSubtask() {
        if (q <= 3000) return true;
        for (const ii &query : queries)
            if (query.first != 0) return false;
        return true;
    };

    void spfa(int s) {
        for (int u = 0; u < n; u++) dist[u] = INF;

        queue<int> q;
        dist[s] = 0;
        q.push(s);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            inQueue[u] = false;

            for (ii e : adj[u]) {
                int v = e.first, w = e.second;
                if (minimize(dist[v], dist[u] + w)) {
                    if (!inQueue[v]) {
                        inQueue[v] = true;
                        q.push(v);
                    };
                };
            };
        };
    };

    void Solve() {
        for (int i = 0; i < q; i++) {
            int u = queries[i].first, v = queries[i].second;
            qu[u].push_back(make_pair(v, i));
        };

        for (int u = 0; u < n; u++) {
            if (qu[u].empty()) continue;

            spfa(u);

            for (const ii &q : qu[u]) {
                int v = q.first, idx = q.second;
                ans[idx] = (dist[v] == INF ? -1 : dist[v]);
            };
        };

        for (int i = 0; i < q; i++) cout << ans[i] << '\n';
    };
};  // namespace SUBTASK_234

namespace SUBTASK_5 {
    const int N = MAX_N;

    struct Matrix {
        int c[5][5];

        Matrix() {
            for (int i = 0; i < 5; i++)
                for (int j = 0; j < 5; j++) c[i][j] = INF;
        };

        Matrix operator*(const Matrix &other) const {
            Matrix res;
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    for (int k = 0; k < 5; k++) {
                        minimize(res.c[i][j], c[i][k] + other.c[k][j]);
                    };
                };
            };
            return res;
        };

        void print() {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    cout << c[i][j] << ' ';
                };
                cout << endl;
            };
        };
    } st[18][N + 5];

    void Solve() {
        for (int u = 0; u < n; u++) {
            for (ii e : adj[u]) {
                int v = e.first, w = e.second;
                st[0][u / k].c[u % k][v % k] = w;  // min dist (u, v) from layer (u/k) to (layer(v/k) = layer(u/k + 2^0))
            };
        };

        int lim = (n + k - 1) / k;
        for (int j = 1; (1 << j) <= lim; j++) {
            for (int layer = 0; layer + (1 << j) - 1 <= lim; layer++) {
                st[j][layer] = st[j - 1][layer] * st[j - 1][layer + (1 << (j - 1))];
            };
        };

        for (const ii &q : queries) {
            int u = q.first, v = q.second;

            int layerU = u / k;
            int layerV = v / k;

            if (layerU >= layerV) {
                cout << (u == v ? 0 : -1) << '\n';
                continue;
            };

            int d = layerV - layerU;

            Matrix ans;
            for (int i = 0; i < 5; i++) ans.c[i][i] = 0;
            int curLayer = layerU;
            for (int j = 0; (1 << j) <= layerV; j++) {
                if (d >> j & 1) {
                    ans = ans * st[j][curLayer];
                    curLayer += 1 << j;
                };
            };

            int res = ans.c[u % k][v % k] == INF ? -1 : ans.c[u % k][v % k];
            cout << res << '\n';
        };
    };

};  // namespace SUBTASK_5

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> k >> n >> m >> q;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(ii(v, w));
    };

    queries.resize(q);
    for (ii &query : queries) cin >> query.first >> query.second;

    SUBTASK_5::Solve();
};

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:202:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:203:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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