Submission #502422

#	Time	Username	Problem	Language	Result	Execution time	Memory
502422		Lobo	Toll (BOI17_toll)	C++17	0 / 100	15 ms	460 KiB

toll

#include<bits/stdc++.h>
using namespace std;

/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 105000

ll k, n, m, q, d[maxn][20][7][7];

void solve() {
    cin >> k >> n >> m >> q;

    for(ii br = 0; br <= (n-1)/k; br++) {
        for(ii pot = 0; pot <= 18; pot++) {
            for(ii i = 0; i < k; i++) {
                for(ii j = 0; j < k; j++) {
                    d[br][pot][i][j] = INFii;
                }
            }
        }
    }



    for(ii i = 0; i < m; i++) {
        ii u, v, w;
        cin >> u >> v >> w;
        d[u/k][0][u%k][v%k] = w;
    }

    for(ii pot = 1; pot <= 18; pot++) {
        for(ii br = 0; br <= (n-1)/k; br++) {
            ii mdbr = br+(1<<(pot-1));
            ii nxbr = br+(1<<pot);
            if(nxbr > (n-1)/k) {
                continue;
            }

            for(ii i = 0; i < k; i++) {
                for(ii md = 0; md < k; md++) {
                    for(ii nx = 0; nx < k; nx++) {
                        d[br][pot][i][nx] = min(d[br][pot][i][nx], d[br][pot-1][i][md] + d[mdbr][pot-1][md][nx]);
                    } 
                }
            }
        }
    }

    while(q--) {
        ii beg, des;
        cin >> beg >> des;

        vector<ll> ans;
        for(ii i = 0; i < k; i++) {
            ans.pb(INFii);
        }
        ans[beg%k] = 0;

        ii br = beg/k;
        for(ii pot = 18; pot >= 0; pot--) {
            ii nxbr = br+(1<<pot);
            if(nxbr > des/k) continue;

            vector<ll> nans;

            for(ii i = 0; i < k; i++) {
                nans.pb(INFii);
            }

            for(ii i = 0; i < k; i++) {
                for(ii nx = 0; nx < k; nx++) {
                    nans[nx] = min(nans[nx], ans[i] + d[br][pot][i][nx]);
                }
            }

            ans = nans;
            br = nxbr;
        }

        ll ans1 = ans[des%k];
        if(ans1 >= INFii) {
            cout << -1 << endl;
        }
        else {
            cout << ans1 << endl;
        }
    }

    for(ii pot = 0; pot <= 18; pot++) {
        for(ii br = 0; br <= (n-1)/k; br++) {
            ii nxbr = br+(1<<pot);
            if(nxbr > (n-1)/k) {
                continue;
            }

            for(ii i = 0; i < k; i++) {
                for(ii nx = 0; nx < k; nx++) {
                    // cout << br << " " << pot << " " << i << " " << nx << " == " << d[br][pot][i][nx] << endl;
                    // cout << br*k+i << " -> " << nxbr*k+nx << " == " << endl;
                }     
            }
        }
    }




}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    #endif

    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:131:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     freopen("in.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:132:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     freopen("out.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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