Submission #368143

#	Time	Username	Problem	Language	Result	Execution time	Memory
368143		Sorting	Toll (BOI17_toll)	C++17	100 / 100	160 ms	13036 KiB

toll

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 3;
const int O = 1e4 + 3;
const int K = 5 + 3;
const int INF = 1e9;

void check_min(int &a, int b){ a = a < b ? a : b; }

int k, n, m, o;
vector<array<int, 3>> adj[N], rev_adj[N];
int ans[O], lef[N], rig[N];

void dnc(int l, int r, const vector<array<int, 3>> &queries){
    if(queries.empty()) return;
    if(l == r){
        for(auto [a, b, idx]: queries)
            ans[idx] = -1;
        return;
    }

    int mid = (l + r) >> 1;

    vector<array<int, 3>> todo[2];
    vector<array<int, 3>> curr;
    for(auto [a, b, i]: queries){
        if(a / k <= mid && mid <= b / k){
            curr.push_back({a, b, i});
            continue;
        }

        if(b / k < mid) todo[0].push_back({a, b, i});
        else todo[1].push_back({a, b, i});
    }

    for(int i = 0; i < k; ++i){
        for(int j = 0; j < k; ++j)
            lef[mid * k + j] = (j == i) ? 0 : INF;
        for(int j2 = mid - 1; j2 >= l; --j2){
            for(int j = 0; j < k; ++j)
                lef[j2 * k + j] = INF;
            for(auto [from, to, t]: rev_adj[j2 + 1])
                check_min(lef[to], lef[from] + t);
        }

        for(int j = 0; j < k; ++j)
            rig[mid * k + j] = (j == i) ? 0 : INF;
        for(int j2 = mid + 1; j2 <= r; ++j2){
            for(int j = 0; j < k; ++j)
                rig[j2 * k + j] = INF;
            for(auto [from, to, t]: adj[j2 - 1])
                check_min(rig[to], rig[from] + t);
        }

        for(auto [a, b, idx]: curr)
            check_min(ans[idx], lef[a] + rig[b]);
    }

    dnc(l, mid - 1, todo[0]), dnc(mid + 1, r, todo[1]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> k >> n >> m >> o;
    for(int i = 0; i < m; ++i){
        int a, b, t;
        cin >> a >> b >> t;
        adj[a / k].push_back({a, b, t});
        rev_adj[b / k].push_back({b, a, t});
    }

    vector<array<int, 3>> queries;
    for(int i = 0; i < o; ++i){
        int a, b;
        cin >> a >> b;
        queries.push_back({a, b, i});
    }

    fill(ans, ans + o, INF);
    dnc(0, n / k, queries);

    for(int i = 0; i < o; ++i)
        if(ans[i] == INF)
            ans[i] = -1;

    for(int i = 0; i < o; ++i)
        cout << ans[i] << "\n";
}

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