Submission #869084

#	Time	Username	Problem	Language	Result	Execution time	Memory
869084		quandlm	Toll (BOI17_toll)	C++14	100 / 100	98 ms	191052 KiB

toll

#include <bits/stdc++.h>
#define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define pi pair<int,int>
#define ple tuple<int,int,int>
#define fi first
#define se second
#define ii make_pair
#define isz(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define int long long

using namespace std;

const int N = 5e4 + 10;
const int lg = 17;
const int inf = 1e18;

int n, q, k,  m, lim;
bool have[N][lg+2];
vector<int> adj[N];
int res[5][5], tmp[5][5], dp[N][lg+2][5][5];

void minimize (int &a, int b) {
     a = min(a, b);
}

int bit (int i, int a) {
    return (a >> i) & 1;
}

void Merge (int h[5][5], int g[5][5], int f[5][5]) {
     for(int x = 0; x < k; ++x) {
         for(int y = 0; y < k; ++y) {
            for (int z = 0; z < k; ++z) {
                 minimize(h[x][z], g[x][y] + f[y][z]);
            }
         }
     }
}

void reset(int x[5][5]) {
     for(int i=0; i<k;++i) {
         for(int j=0;j<k;++j) {
             x[i][j]=inf;
         }
     }
}

void recur() {
     for(int i=0;i<k;++i) {
         for(int j=0;j<k;++j) {
             res[i][j]=tmp[i][j];
         }
     }
}

int solve (int u, int v) {
    int st = u / k;
    int ed = v / k;
    int cur = st;
    for (int i = lg; i >= 0; --i) {
         if (cur + (1 << i) <= ed) {
             reset(tmp);
             Merge(tmp, res, dp[cur][i]);
             recur();
             cur += (1 << i);
         }
    }
    int ans = res[u%k][v%k];
    if (ans == inf) ans=-1;
    return ans;
}

main () {
    file("toll");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

    FOR(i,0,n) {
        FOR(j,0,lg) {
            FOR(x,0,k) {
                 FOR(y,0,k) {
                      dp[i][j][x][y] = inf;
                 }
            }
        }
    }

    FOR(i,1,m) {
        int u,v,w; cin >> u >> v >> w;
        dp[u/k][0][u%k][v%k] = w;
    }

    lim = n / k + 1;

    for (int j = 1; j <= lg; ++j) {
         for (int i = 0; i + (1 << j) - 1 <= lim; ++i) {
              Merge(dp[i][j], dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
         }
    }


    while(q--) {
         int s, t; cin >> s >> t;
         reset(res);
         for (int i = 0; i < k; ++i) res[i][i] = 0;
         cout << solve(s, t) << '\n';
    }
}


/// code by yourlove

Compilation message (stderr)

toll.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main () {
      | ^~~~
toll.cpp: In function 'int main()':
toll.cpp:2:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:78:5: note: in expansion of macro 'file'
   78 |     file("toll");
      |     ^~~~
toll.cpp:2:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:78:5: note: in expansion of macro 'file'
   78 |     file("toll");
      |     ^~~~

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