Submission #1261994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261994		dangheo	Toll (BOI17_toll)	C++20	100 / 100	99 ms	39628 KiB

toll

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>

#define hyathu main
#define popcorn __builtin_popcount

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int mmb = 5e4 + 69;
constexpr ll inf = 4e18;
const ld pi = atan(1) * 4;

int n, q, m, k, a, b;
ll d[mmb][20][5];

void readData(){
    cin >> k >> n >> m >> q;
    fill(d[0][0], d[n + 1][0], inf);
    int x, y;
    ll w;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y >> w;;
        y %= k;
        d[x][0][y] = min(d[x][0][y], w);
    }
}

void solve(){
    for(int j = 1; j <= 19; ++j){
        for(int i = 0; i < n; ++i){
            if(i / k + (1 << j) > n / k) break;
            int ly = i / k + (1 << (j - 1));
            for(int nx = 0; nx < k; ++nx){
                for(int bt = 0; bt < k; ++bt)
                    d[i][j][nx] = min(d[i][j][nx], d[i][j - 1][bt] + d[ly * k + bt][j - 1][nx]);
            }
        }
    }
    
    while(q--){
        cin >> a >> b;
        int la = a / k;
        int lb = b / k;
        int step = 19;
        ll mn[5], nx[5];
        fill(mn, mn + k, inf);
        fill(nx, nx + k, inf);
        mn[a % k] = 0;
        while(step >= 0){
            if(la + (1 << step) <= lb){
                int nl = la + (1 << step);
                for(int i = 0; i < k; ++i){
                    for(int j = 0; j < k; ++j)
                        nx[j] = min(nx[j], mn[i] + d[la * k + i][step][j]);
                }
                copy(nx, nx + k, mn);
                la = nl;
                fill(nx, nx + k, inf);
            }
            --step;
        }
        cout << (mn[b % k] == inf ? -1 : mn[b % k]) << "\n";
    }
}

#define filename "test"

int hyathu(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    #ifdef dangheo
    freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    #else
    //freopen(filename".INP", "r", stdin);
    //freopen(filename".OUT", "w", stdout);
    #endif
    
    readData();
    solve();
    
    return 0;
}

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