Submission #636561

#	Time	Username	Problem	Language	Result	Execution time	Memory
636561		erto	Toll (BOI17_toll)	C++17	100 / 100	128 ms	86740 KiB

toll

#include <bits/stdc++.h>
typedef long long int ll;
#define INF (ll)(1e9 + 7)
#define INF2 998244353ll
#define N (ll)(1e5 + 5)
using namespace std;
//#define int ll
#define lsb(x) (x & (-x))

int n, m, k, g, h, o, t;
int dp[50001][17][5][5];
int temp[5][5], ans[5][5];

void comb(int res[5][5], int a[5][5], int b[5][5]){
    for(int x=0; x<k; x++){
        for(int y=0; y<k; y++){
            for(int z=0; z<k; z++){
                res[x][z] = min(res[x][z], a[x][y] + b[y][z]);
            }
        }
    }
}

void solve(){
    memset(dp, 0x3f, sizeof(dp));
    cin >> k >> n >> m >> o;
    for(int i=1; i<=m; i++){
        cin >> g >> h >> t;
        dp[g / k][0][g % k][h % k] = t;
    }

    for(int i=1; i<17; i++){
        for(int j=0; j + (1 << i) < (n + k - 1) / k; j++){
            comb(dp[j][i], dp[j][i - 1], dp[j + (1 << i - 1)][i - 1]);
        }
    }

    for(int i=1; i<=o; i++){
        cin >> g >> h;
        memset(ans, 0x3f, sizeof(ans));
        for(int i=0; i<k; i++)ans[i][i] = 0;
        int fr = g / k, to = h / k;
        for(int i=16; ~i; i--){
            if(fr + (1 << i) <= to){
                memset(temp, 0x3f, sizeof(temp));
                comb(temp, ans, dp[fr][i]);
                fr += 1 << i;
                memcpy(ans, temp, sizeof(ans));
            }
        }
        if(ans[g % k][h % k] == 0x3f3f3f3f)cout << "-1\n";
        else{
            cout << ans[g % k][h % k] << '\n';
        }
    }
}   
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--){
        solve();
    }
}

Compilation message (stderr)

toll.cpp: In function 'void solve()':
toll.cpp:34:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |             comb(dp[j][i], dp[j][i - 1], dp[j + (1 << i - 1)][i - 1]);
      |                                                       ~~^~~

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