Submission #1199356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199356		zyadhany	Toll (BOI17_toll)	C++20	100 / 100	436 ms	312756 KiB

toll

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
 
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<long long>
#define vii vector<vi>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;
 
const int MODE = 1e9+7;

struct Matrix {
    ll n;
    vii a;
    Matrix(ll n) : n(n), a(n, vi(n, INT32_MAX)) {}
    Matrix operator*(const Matrix &b) const {
        Matrix c(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (a[i][k] != INT32_MAX && b.a[k][j] != INT32_MAX)
                    c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]) % MODE;
                }
            }
        }
        return c;
    }
};



void solve(int tc) {
    ll k, n, m, q;
    cin >> k >> n >> m >> q;

    vector<vector<Matrix>> X(18, vector<Matrix>(n, Matrix(k)));
    for (int i = 0; i < m; i++)
    {
        ll u, v, w; cin >> u >> v >> w;
        X[0][u/k].a[u%k][v%k] = w;
    }
    
    for (int j = 1; j < 18; j++)
    {
        for (int i = 0; i < n; i++)
        {
            if ((i+(1<<(j-1))) >= n) continue;
            X[j][i] = X[j-1][i] * X[j-1][i+(1<<(j-1))];
        }
    }
    
    while (q--)
    {
        ll l, r; cin >> l >> r;
        ll lvl1 = l / k, lvl2 = r / k;
        
        if (l == r) cout << "0\n";
        else if (lvl1>=lvl2) cout << "-1\n";
        else {
            Matrix res(k);
            res.a[l%k][l%k] = 0;
            ll p = lvl2-lvl1;
            ll at = l/k;
            for (int i = 0; i < 18; i++)
            {
                if (p & (1<<i)) {
                    res = res * X[i][at];
                    at += 1<<i;
                }
            }
            
            ll sol = res.a[l%k][r%k];
            if (sol == INT32_MAX) cout << "-1\n";
            else cout << sol << '\n';
        }
    }
}

 
 
signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;    
 
    // freopen("lazy.in", "r", stdin);
    // freopen("lazy.out", "w", stdout);
 
    // cin >> size;
    for (int i = 1; i <= size; i++) solve(i);
    return 0;
}

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