Submission #1290556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290556		monaxia	Toll (BOI17_toll)	C++20	49 / 100	41 ms	9828 KiB

toll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds; 

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

constexpr ull Mod = (119 << 23) | 1;
constexpr ull sqr = 223;
constexpr ld eps = 1e-9;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random_ll(ll l, ll r) {if (l > r) return -1; return uniform_int_distribution<ll>(l, r)(rng);}


int k, n, m, Q;

void solve(){

    cin >> k >> n >> m >> Q;
    
    int dp[(n - 1) / k + 1][__lg(n) + 1][k][k];
    memset(dp, -1, sizeof(dp));

    for(int i = 1; i <= m; i ++){
        int a, b, t;
        cin >> a >> b >> t;

        dp[a / k][0][a % k][b % k] = t;
    }

    for(int j = 1; j < __lg(n); j ++){
        for(int i = 0; i + (1 << j) <= (n - 1) / k; i ++){

            for(int a = 0; a < k; a ++){
                for(int c = 0; c < k; c ++){
                    for(int b = 0; b < k; b ++){
                        if(dp[i][(j - 1)][a][b] != -1 && dp[i + (1 << (j - 1))][j - 1][b][c] != -1){
                            if(dp[i][j][a][c] == -1) dp[i][j][a][c] = INT_MAX;

                            dp[i][j][a][c] = min(dp[i][j][a][c], dp[i][j - 1][a][b] + dp[i + (1 << (j - 1))][j - 1][b][c]);
                        }
                    }
                }
            }
        }
    }

    while(Q --){
        int a, b;
        cin >> a >> b;

        int cur = a / k;
        vector <int> ans(k, INT_MAX), mid(k, INT_MAX);

        bool bb = 1;


        for(int _ = __lg(n); _ >= 0; _ --){
            if(cur + (1 << _) > b / k) continue;

            if(bb){
                // cout << a << " " << b << "\n";
                // cout << cur << " " << cur + _ << " " << a % k << " " << "\n";
                for(int i = 0; i < k; i ++){
                    if(dp[cur][_][a % k][i] != -1) ans[i] = dp[cur][_][a % k][i];
                    // cout << i << " " << b % k << ' ' << dp[cur][_][a % k][i] << "\n";
                }

                cur += (1 << _);

                bb = 0;

                continue;
            }

            fill(all(mid), INT_MAX);

            for(int i = 0; i < k; i ++){
                for(int j = 0; j < k; j ++){
                    if(ans[i] != INT_MAX && dp[cur][_][i][j] != -1) mid[j] = min(mid[j], ans[i] + dp[cur][_][i][j]);
                }
            }

            cur += (1 << _);

            swap(ans, mid);
        }

        if(ans[b % k] == INT_MAX) ans[b % k] = - 1;
        cout << ans[b % k] << "\n";
    }
}

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

    if(fopen("placeholder.inp", "r")){
        freopen("placeholder.inp", "r", stdin);
        freopen("placeholder.out", "w", stdout);
    }

    int t = 1;

    // cin >> t;

    while(t --){
        solve();
        cout << "\n";
    }

    cerr << "Code time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}

// Whose eyes are those eyes?

Compilation message (stderr)

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

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