Submission #480714

#	Time	Username	Problem	Language	Result	Execution time	Memory
480714		hidden1	Toll (BOI17_toll)	C++14	100 / 100	238 ms	32964 KiB

toll

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
#ifndef LOCAL
#define cerr if(false) cerr
#endif

typedef vector<vector<ll> > mat;

const ll MAX_N = 1e5 + 10;
ll n, m, k, q;

mat mult(const mat &a, const mat &b) {
    mat ret = mat(k, vector<ll>(k, mod));
    if(a.empty()) { return b; }
    if(b.empty()) { return a; }
    for(ll i = 0; i < k; i ++) {
        for(ll j = 0; j < k; j ++) {
            for(ll mid = 0; mid < k; mid ++) {
                chkmin(ret[i][j], a[i][mid] + b[mid][j]);
            }
        }
    }
    return ret;
}

vector<pair<ll, ll> > g[MAX_N];

mat prec[MAX_N];
mat tree[4 * MAX_N];

void build(int curr, int l, int r) {
    if(l == r) {
        tree[curr] = prec[l];
        return;
    }
    int m = (l + r) / 2ll;
    build(curr * 2, l, m);
    build(curr * 2 + 1, m + 1, r);
    tree[curr] = mult(tree[curr * 2], tree[curr * 2 + 1]);
}

mat quer(int curr, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) {
        return tree[curr];
    } else if(ql > r || l > qr) {
        return {};
    }
    int m = (l + r) / 2ll;
    return mult(
            quer(curr * 2, l, m, ql, qr),
            quer(curr * 2 + 1, m + 1, r, ql, qr)
        );
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> k >> n >> m >> q;
    for(ll i = 0; i < m; i ++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for(ll i = 0; i < n; i += k) {
        prec[i / k] = mat(k, vector<ll>(k, mod));
        for(ll j = i; j < i + k; j ++) {
            for(auto it : g[j]) {
                chkmin(prec[i / k][j % k][it.first % k], it.second);
            }
        }
    }
    build(1, 0, MAX_N - 1);
    while(q --) {
        ll a, b;
        cin >> a >> b;
        if(a / k >= b / k) {
            cout << -1 << endl; 
            continue;
        } 
        mat ret = quer(1, 0, MAX_N - 1, a / k, b / k - 1);

        if(ret[a % k][b % k] == mod) {
            cout << -1 << endl; 
        } else {
            cout << ret[a % k][b % k] << endl;
        }
    }
    return 0;
}

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