Submission #1069489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069489		Requiem	Toll (BOI17_toll)	C++17	0 / 100	216 ms	86608 KiB

toll

#include<bits/stdc++.h>
//#define int long long
#define inf 1e9
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define TASKNAME "Toll"
using namespace std;

template<typename T> bool minimize(T &a, T b){  if (a > b) {a = b; return true; } return false; }

struct matrix{
    vector<vector<int>> mat;
    int r, c;
    matrix(int _r = 0, int _c = 0){
        r = _r, c = _c;
        mat.resize(_r, vector<int>(_c, inf));
    }

    void print(){
        FOR(i, 0, r - 1){
            FOR(j, 0, c - 1){
                printf("%lld ", mat[i][j]);
            }
            printf("\n");
        }
    }
};

matrix mul(matrix a, matrix b){
    matrix res(a.r, b.c);;
    FOR(i, 0, a.r - 1){
        FOR(j, 0, b.c - 1){
            FOR(k, 0, a.c - 1){
                minimize(res.mat[i][j], a.mat[i][k] + b.mat[k][j]);
            }
        }
    }
    return res;
}

const int MAXN = 5e4 + 9;
int n, m, q, k;
vector<matrix> transD;

matrix P[20][MAXN];
int mask[MAXN];

void DnC(int l, int r, int lvl){
    if (l == r) return;
    int mid = (l + r) >> 1;
    FOR(i, l, r) P[lvl][i] = matrix(k, k);
    P[lvl][mid] = transD[mid];
    P[lvl][mid + 1] = transD[mid + 1];
//    cerr << l << ' ' << r << endl;
//
    FORD(i, mid - 1, l) P[lvl][mid] = mul(transD[i], P[lvl][mid + 1]);
    FOR(i, mid + 2, r) P[lvl][mid] = mul(P[lvl][mid + 1], transD[i]);
//
    FOR(i, mid + 1, r) mask[i] ^= (1LL << lvl);
    DnC(l, mid, lvl + 1);
    DnC(mid + 1, r, lvl + 1);
}

matrix Query(int l, int r){
    if (l == r) return transD[l];
    else {
        int bit = __builtin_ctz(mask[l] ^ mask[r]);
        return mul(P[bit][l], P[bit][r]);
    }
}
void solve(){
    cin >> k >> n >> m >> q;
    transD.resize(n / k + 9, matrix(k, k));
    FOR(i, 0, m - 1){
        int u, v, t;
        cin >> u >> v >> t;
        transD[u / k].mat[u % k][v % k] = t;
    }
//    FOR(i, 0, n / k - 1){
//        FOR(j, 0, k - 1){
//            FOR(t, 0, k - 1){
//                printf("%lld ", transD[i].mat[j][t]);
//            }
//            printf("\n");
//        }
//        printf("\n");
//    }
    //transD[i]: ma tran de chuyen tu block i len block i + 1.
    DnC(0, n / k - 1, 0);
//
    FOR(i, 0, q - 1){
        int u, v;
        cin >> u >> v;
        if (u / k == v / k) printf("-1\n");
        else{
            matrix start(k, k);
            start.mat[u % k][u % k] = 0;
            start = mul(start, Query(u / k, v / k - 1));
//            start.print();
            if (start.mat[u % k][v % k] < inf) {
                printf("%lld\n", start.mat[u % k][v % k]);
            }
            else printf("-1\n");
        }
    }


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

}

Compilation message (stderr)

toll.cpp: In member function 'void matrix::print()':
toll.cpp:22:28: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wformat=]
   22 |                 printf("%lld ", mat[i][j]);
      |                         ~~~^
      |                            |
      |                            long long int
      |                         %d
toll.cpp: In function 'void solve()':
toll.cpp:101:28: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wformat=]
  101 |                 printf("%lld\n", start.mat[u % k][v % k]);
      |                         ~~~^
      |                            |
      |                            long long int
      |                         %d
toll.cpp: At global scope:
toll.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main(){
      | ^~~~
toll.cpp: In function 'int main()':
toll.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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