Submission #1147366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147366		akamizane	Toll (BOI17_toll)	C++20	100 / 100	79 ms	83532 KiB

toll

#include<bits/stdc++.h>

using namespace std;
 

#define debug(...) 40

 
using ll = long long;
using pii = pair<long long, long long>;
using db = long double;

// #define int long long
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}

const int maxn = 1e5 + 5;
const int mod = 998244353;
const ll inf = 1e18;

int dp[50005][17][5][5], ans[5][5], tmp[5][5];
int k, m, n, o;

void combine(int target[5][5], int a[5][5], int b[5][5]){
    REP(x, k) REP(y, k) REP(z, k) target[x][y] = min(target[x][y], a[x][z] + b[z][y]);
}

void solve(){
  cin >> k >> n >> m >> o;
  memset(dp, 0x3f, sizeof dp);
  while(m--){
    int a, b, t;
    cin >> a >> b >> t;
    debug(a, b, t);
    dp[a / k][0][a % k][b % k] = t;
  }
  for (int j = 1; j < 17; j++){
    for (int i = 0; i + (1 << j) < (n + k - 1) / k; i++){
        combine(dp[i][j], dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
    }
  }
  while(o--){
    int a, b;
    cin >> a >> b;
    memset(ans, 0x3f, sizeof ans);
    REP(i, 5) ans[i][i] = 0;
    for (int u = a / k, v = b / k, cnt = 16; cnt >= 0; cnt--){
        if (u + (1 << cnt) <= v){
        memset(tmp, 0x3f, sizeof tmp);
        combine(tmp, ans, dp[u][cnt]);
        memcpy(ans, tmp, sizeof ans);
        u += (1 << cnt);
    }
    }
    cout << (ans[a % k][b % k] == 0x3f3f3f3f ? -1 : ans[a % k][b % k]) << '\n';
  }
  
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    solve();
    cout << "\n";
  }
  return 0;
}

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