Submission #1261943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261943		4o2a	Toll (BOI17_toll)	C++20	100 / 100	612 ms	7576 KiB

toll

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define _F "what"
using namespace std;
typedef long long ll;

constexpr int N = 5e4;
constexpr ll INF = 1e18;
int k, n, m, q;
vector<vector<ll>> dist(N, vector<ll>(5, INF)), W(N, vector<ll>(5, INF));

ll calc(int u, int v)
{
    vector<ll> D(k, INF), pre(k); D[u%k] = 0;
    while (u/k < v/k)
    {
        pre = D;
        fill(D.begin(), D.end(), INF);
        for (int j = 0; j < k; ++j)
            for (int x = (u/k)*k; x < (u/k + 1)*k; ++x)
                D[j] = min(D[j], pre[x%k] + W[x][j]);
        u += k;
    }
    return D[v%k];
}

void solve()
{
    cin>>k>>n>>m>>q;
    while (m--)
    {
        int u, v, t; cin>>u>>v>>t;
        W[u][v%k] = t;
    }
    int S = ((250)/k)*k;
    for (int i = 0; i < n; ++i)
        for (int j = ((i + S)/k)*k; j < ((i + S)/k + 1)*k && j < n; ++j)
            dist[i][j%k] = calc(i, j);
    vector<ll> D(k), pre(k);
    while (q--)
    {
        int u, v; cin>>u>>v;
        fill(D.begin(), D.end(), INF); D[u%k] = 0;
        while (v - u >= S)
        {
            pre = D;
            fill(D.begin(), D.end(), INF);
            for (int j = 0; j < k; ++j)
                for (int x = (u/k)*k; x < (u/k + 1)*k && x < n; ++x)
                    D[j] = min(D[j], pre[x%k] + dist[x][j]);
            u += S;
        }
        ll res = INF;
        for (int j = (u/k)*k; j < (u/k + 1)*k && j < n; ++j)
            res = min(res, calc(j, v) + D[j%k]);
        cout<<(res == INF ? -1 : res)<<"\n";
    }
}

int main()
{
    if (fopen(_F".INP", "r"))
    {
        freopen(_F".INP", "r", stdin);
        freopen(_F".OUT", "w", stdout);
    }
    else if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        //freopen("test.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int Test = 1; //cin>>Test;
    while (Test--) solve();
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(_F".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(_F".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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