Submission #955858

#	Time	Username	Problem	Language	Result	Execution time	Memory
955858		Flan312	Toll (BOI17_toll)	C++17	100 / 100	113 ms	160344 KiB

toll

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 5e4 + 2;
int n, m, q, k;
ll dp[nmax][16][5][5], ans[5], nxt[5];
/*
dp[u][i][remU][remV]: đường đi ngắn nhất từ u*k + remU -> (u + 2^i - 1) * k + remv
đường ngắn nhất từ đỉnh remU của tầng u đến đỉnh remV tầng u + 2^i - 1
*/
void merge(int i, int j, int ii, int jj, int iii, int jjj)
{
    for (int ru = 0; ru < k; ++ru)
        for (int rv = 0; rv < k; ++rv)
            for (int rt = 0; rt < k; ++rt)
                dp[i][j][ru][rv] = min(dp[i][j][ru][rv], dp[ii][jj][ru][rt] + dp[iii][jjj][rt][rv]);
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> k >> n >> m >> q;
    memset(dp, 0x3f, sizeof dp);
    while(m--)
    {
        int a, b, t;
        cin >> a >> b >> t;
        dp[a / k][0][a % k][b % k] = t;
    }
    for (int j = 1; (1 << j) <= n / k; ++j)
        for (int i = 0; i + (1 << j) - 1 <= n / k; ++i)
            merge(i, j, i, j - 1, i + (1 << j - 1), j - 1);
    while(q--)
    {
        int a, b;
        cin >> a >> b;
        if (a == b) {cout << "0\n"; continue;}
        if (a / k >= b / k) {cout << "-1\n"; continue;}
        for (int i = 0; i < k; ++i)
            ans[i] = 1e18;
        ans[a % k] = 0;
        int layer = a / k, dist = b / k - a / k;
        for (int j = 0; (1 << j) <= dist; ++j)
            if (dist >> j & 1)
            {
                for (int r = 0; r < k; ++r) nxt[r] = 1e18;
                for (int x = 0; x < k; ++x)
                    for (int y = 0; y < k; ++y)
                        nxt[x] = min(nxt[x], ans[y] + dp[layer][j][y][x]);
                layer += (1 << j);
                for (int r = 0; r < k; ++r)
                    swap(ans[r], nxt[r]);
            }
        cout << (ans[b % k] >= 1e18 ? -1 : ans[b % k]) << '\n';
    }
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:41:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   41 |             merge(i, j, i, j - 1, i + (1 << j - 1), j - 1);
      |                                             ~~^~~
toll.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:29:31: note: in expansion of macro 'nx'
   29 |     if (ifstream(task".inp")) nx
      |                               ^~
toll.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:29:31: note: in expansion of macro 'nx'
   29 |     if (ifstream(task".inp")) nx
      |                               ^~

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