제출 #476234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476234		Karliver	Toll (BOI17_toll)	C++14	100 / 100	137 ms	86896 KiB

toll

    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 5e4 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}
int n, k, m, q;
const int MX = 17;
int F[N][MX][5][5], tmp[5][5], ans[5][5];

void comb(int tar[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)
                tar[x][y] = min(tar[x][y], a[x][z] + b[z][y]);
}

void solve() {


    
    cin >> k >> n >> m >> q;

    memset(F, 0x3f, sizeof F);
    while(m--) {
        int a, b, t;
        cin >> a >> b >> t;
        F[a / k][0][a % k][b % k] = t;
    }

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

    while(q--) {
        int a, b;
        cin >> a >> b;
        memset(ans, 0x3f, sizeof(ans));
        forn(i, 5) ans[i][i] = 0;
        for(int cur = a / k, T = b / k,i = MX - 1;~i;--i) {
            if(cur + (1 << i) <= T) {
                memset(tmp, 0x3f, sizeof tmp);
                comb(tmp, ans, F[cur][i]);
                memcpy(ans, tmp, sizeof ans);
                cur += 1 << i;
            }
        }
        cout << (ans[a % k][b % k] == 0x3f3f3f3f ? -1 : ans[a % k][b % k]) << '\n';
    }
    

}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

컴파일 시 표준 에러 (stderr) 메시지

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

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