Submission #998757

#	Time	Username	Problem	Language	Result	Execution time	Memory
998757		iah	Toll (BOI17_toll)	C++14	100 / 100	126 ms	72160 KiB

toll

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

#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

constexpr int inf = 1e9;

int k;

vector < vector < vector < vector < int > > > > d;
vector < vector < int > > ans, tmp;

void combine(vector < vector < int > > &res, vector < vector < int > > &a, vector < vector < int > > &b) {
  for (int x = 0; x < k; x ++) {
    for (int y = 0; y < k; y ++) {
      for (int z = 0; z < k; z ++) {
        res[x][y] = min(res[x][y], a[x][z] + b[z][y]);
      }
    }
  }
}

signed main() {
  if (fopen(NAME".inp", "r")) {
    freopen(NAME".inp", "r", stdin);
    freopen(NAME".out", "w", stdout);
  }
  cin.tie(0)->sync_with_stdio(0);

  int n, m, q;
  cin >> k >> n >> m >> q;
  n --;
  n /= k;

  d.assign(n + 1, vector < vector < vector < int > > > (16, vector < vector < int > > (k, vector < int > (k, inf))));
  ans.assign(k, vector < int > (k, 0));
  tmp.assign(k, vector < int > (k, 0));

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

  for (int j = 1; mask(j) <= n; j ++) {
    for (int i = 0; i + mask(j) <= n; i ++) {
      combine(d[i][j], d[i][j - 1], d[i + mask(j - 1)][j - 1]);

//      cout << j << " " << i << " " << i + mask(j - 1) << "\n";
//      for (int x = 0; x < k; x ++) {
//        for (auto y = 0; y < k; y ++) {
//          cout << d[i][j][x][y] << " ";
//        }
//        cout << "\n";
//      }
//      cout << "\n";
    }
  }

  for (; q --;) {
    int u, v;
    cin >> u >> v;

    int diff = (v / k) - (u / k), stair = u / k;

    for (int i = 0; i < k; i ++) {
      for (int j = 0; j < k; j ++) {
        if (i != j) {
          ans[i][j] = inf;
        }
        else {
          ans[i][j] = 0;
        }
      }
    }


    if (diff < 0) {
      for (int i = 0; i < k; i ++) {
        for (int j = 0; j < k; j ++) {
          ans[i][j] = inf;
        }
      }
    }

    for (int j = 0; mask(j) <= diff; j ++) {
      if (bit(diff, j) && diff > 0) {
        swap(ans, tmp);

        for (int i = 0; i < k; i ++) {
          for (int j = 0; j < k; j ++) {
            ans[i][j] = inf;
          }
        }

        combine(ans, tmp, d[stair][j]);
        stair += mask(j);
      }
    }

    u %= k;
    v %= k;
    cout << (ans[u % k][v % k] == inf ? -1: ans[u % k][v % k]) << "\n";
  }

  return 0;
}

Compilation message (stderr)

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

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