Submission #286805

#	Time	Username	Problem	Language	Result	Execution time	Memory
286805		freerice	Toll (BOI17_toll)	C++17	100 / 100	165 ms	86904 KiB

toll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<long long, long long> pll;
typedef pair<pair<int, int>, int> ppi;
typedef pair<int, pair<int, int> > pip;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int, int> > vpi;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'

#define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
#define FORd(i, a, b) for (int (i) = (a); i >= (b); --i)
#define TRAV(i, x) for (auto& (i) : (x))
#define PRSP(x, a) for (int rv = 0; rv < a; ++rv) {cout << ((rv==0 ? "" : " ")) << x[rv];} cout << endl;
#define mppi(a, b, c) mp(mp((a), (b)), (c))
#define mpip(a, b, c) mp((a), mp((b), (c)))
#define max3(a, b, c) max(max((a), (b)), (c))
#define min3(a, b, c) min(min((a), (b)), (c))

void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	if (name == "")
        return;
    if (name == "input") {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    }
	else {
        freopen((name+".in").c_str(),"r",stdin);
        freopen((name+".out").c_str(),"w",stdout);
    }
}

const int INF = 1000000000;
const int NINF = INT_MIN;
const int MAXLOG = 21;
const int MAXSEG = (1<<18);
const int MUL = 1000001;
const int MOD = 1000000007;
const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    ll operator()(ll x) const {
        return x ^ RANDOM;
    }
};

const int N = 500005;
const int LOGN = 17;
const int K = 5;

int k, m, n, o;
int dp[N][LOGN][K][K];

void combine(int a[K][K], int b[K][K], int c[K][K]) {
    FOR (i, 0, k) {
        FOR (l, 0, k) {
            FOR (j, 0, k) {
                a[i][l] = min(a[i][l], b[i][j] + c[j][l]);
            }
        }
    }
}

int main() {
	chrono::high_resolution_clock::time_point t0 = chrono::high_resolution_clock::now();

	setIO();
    cin >> k >> n >> m >> o;
    FOR (a, 0, n)
        FOR (b, 0, LOGN)
            FOR (c, 0, k)
                FOR (d, 0, k)
                    dp[a][b][c][d] = INF;
    FOR (i, 0, m) {
        int a, b, t;
        cin >> a >> b >> t;
        dp[a/k][0][a%k][b%k] = t;
    }
    FOR (j, 1, LOGN) {
        FOR (i, 0, n) {
            if (i+(1<<j) >= (n+k-1)/k)
                continue;
            combine(dp[i][j], dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
    while (o--) {
        int a, b;
        cin >> a >> b;
        int ans[K][K];
        FOR (i, 0, K) {
            FOR (j, 0, K) {
                if (i==j)
                    ans[i][j] = 0;
                else
                    ans[i][j] = INF;
            }
        }
        int dif = b/k - a/k;
        int cur = a/k;
        FOR (i, 0, LOGN) {
            if (dif & (1<<i)) {
                int tmp[K][K];
                FOR (x, 0, k)
                    FOR (y, 0, k)
                        tmp[x][y] = INF;
                combine(tmp, ans, dp[cur][i]);
                FOR (x, 0, k)
                    FOR (y, 0, k)
                        ans[x][y] = tmp[x][y];
                cur = cur + (1<<i);
            }
        }
        if (ans[a%k][b%k] == INF)
            cout << -1 << '\n';
        else
            cout << ans[a%k][b%k] << '\n';
    }

	chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
//	cout << "TIME: " << chrono::duration_cast<chrono::milliseconds>(t1 - t0).count() << " ms" << endl;
}

Compilation message (stderr)

toll.cpp: In function 'void combine(int (*)[5], int (*)[5], int (*)[5])':
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:72:5: note: in expansion of macro 'FOR'
   72 |     FOR (i, 0, k) {
      |     ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'l' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:73:9: note: in expansion of macro 'FOR'
   73 |         FOR (l, 0, k) {
      |         ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:74:13: note: in expansion of macro 'FOR'
   74 |             FOR (j, 0, k) {
      |             ^~~
toll.cpp: In function 'int main()':
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'a' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:86:5: note: in expansion of macro 'FOR'
   86 |     FOR (a, 0, n)
      |     ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'b' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:87:9: note: in expansion of macro 'FOR'
   87 |         FOR (b, 0, LOGN)
      |         ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'c' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:88:13: note: in expansion of macro 'FOR'
   88 |             FOR (c, 0, k)
      |             ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:89:17: note: in expansion of macro 'FOR'
   89 |                 FOR (d, 0, k)
      |                 ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:91:5: note: in expansion of macro 'FOR'
   91 |     FOR (i, 0, m) {
      |     ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:96:5: note: in expansion of macro 'FOR'
   96 |     FOR (j, 1, LOGN) {
      |     ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:97:9: note: in expansion of macro 'FOR'
   97 |         FOR (i, 0, n) {
      |         ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:107:9: note: in expansion of macro 'FOR'
  107 |         FOR (i, 0, K) {
      |         ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:108:13: note: in expansion of macro 'FOR'
  108 |             FOR (j, 0, K) {
      |             ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:117:9: note: in expansion of macro 'FOR'
  117 |         FOR (i, 0, LOGN) {
      |         ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:120:17: note: in expansion of macro 'FOR'
  120 |                 FOR (x, 0, k)
      |                 ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:121:21: note: in expansion of macro 'FOR'
  121 |                     FOR (y, 0, k)
      |                     ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:124:17: note: in expansion of macro 'FOR'
  124 |                 FOR (x, 0, k)
      |                 ^~~
toll.cpp:27:31: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   27 | #define FOR(i, a, b) for (int (i) = (a); i < (b); ++i)
      |                               ^
toll.cpp:125:21: note: in expansion of macro 'FOR'
  125 |                     FOR (y, 0, k)
      |                     ^~~
toll.cpp:82:44: warning: variable 't0' set but not used [-Wunused-but-set-variable]
   82 |  chrono::high_resolution_clock::time_point t0 = chrono::high_resolution_clock::now();
      |                                            ^~
toll.cpp:136:44: warning: variable 't1' set but not used [-Wunused-but-set-variable]
  136 |  chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
      |                                            ^~
toll.cpp: In function 'void setIO(std::string)':
toll.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   43 |         freopen("output.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   46 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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