Submission #869048

#	Time	Username	Problem	Language	Result	Execution time	Memory
869048		quandlm	Toll (BOI17_toll)	C++14	0 / 100	124 ms	488076 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 = 20;
const int inf = 1e18;

int n, q, k, nxt[N][10], m, lim;
int rmq[N][lg+2][6];
vector<int> adj[N];
int f[50][50], dp[N][lg+5][7][7];

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

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

int solve (int s, int t) {
    for(int i=0;i<=lg;++i) {
        for (int j=0;j<=k; ++j) {
             f[i][j] = inf;
        }
    }
    int sk = s/k;
    int tk = t/k;
    int dis = tk - sk;
    vector<int> vec = {};
    int p = sk;
    for(int j=0; j<=lg; ++j) {
        if (bit(j, dis)) {
            vec.push_back(j);
        }
    }
    for (int j = 0; j < k; ++j) {
         f[0][j] = dp[sk][vec[0]][s%k][j];
    }
    for (int i = 1; i < isz(vec); ++i) {
         for (int x = 0; x < k; ++x) {
              for (int y = 0; y < k; ++y) {
                   int xx = sk + (1 << vec[i-1]);
                   int yy = vec[i] - vec[i-1];
                   minimize(f[i][y], f[i-1][x] + dp[xx][yy][x][y]);
              }
         }
    }
    int res = f[isz(vec)-1][t%k];
    if (res > 1e15) res = -1;
    return res;
}

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;
        adj[u].push_back(v);
    }

    lim = n / k + 1;

    for(int j=1; j<=lg; ++j) {
        for(int i=0; i+(1<<j)-1<=lim; ++i) {
            for(int x=0; x<k; ++x) {
                for (int y=0; y<k; ++y) {
                     for(int z=0; z<k; ++z) {
                         minimize(dp[i][j][x][y], dp[i][j-1][x][z] + dp[i+(1<<(j-1))][j-1][z][y]);
                     }
                }
            }
        }
    }

//    cout << dp[0][1][]
//    cout << dp[0][1][0][2] << endl;

    while(q--) {
         int s, t; cin >> s >> t;
         if (s / k == t / k) {
             cout << -1 << '\n';
             continue;
         }

         cout << solve(s, t) << '\n';
    }
}


/// code by yourlove

Compilation message (stderr)

toll.cpp: In function 'long long int solve(long long int, long long int)':
toll.cpp:44:9: warning: unused variable 'p' [-Wunused-variable]
   44 |     int p = sk;
      |         ^
toll.cpp: At global scope:
toll.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | 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:68:5: note: in expansion of macro 'file'
   68 |     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:68:5: note: in expansion of macro 'file'
   68 |     file("toll");
      |     ^~~~

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