oj.uz

Submission #998752

# Submission time Handle Problem Language Result Execution time Memory
998752 2024-06-14T15:58:41 Z iah Toll (BOI17_toll) C++14
7 / 100
 111 ms 72048 KB 
#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 ++) {
        ans[i][j] = 0;
      }
    }

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

    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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 72016 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 110 ms 71856 KB Output is correct
9 Correct 108 ms 72048 KB Output is correct
10 Correct 88 ms 71576 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 61776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 72016 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 110 ms 71856 KB Output is correct
9 Correct 108 ms 72048 KB Output is correct
10 Correct 88 ms 71576 KB Output is correct
11 Incorrect 95 ms 61776 KB Output isn't correct
12 Halted 0 ms 0 KB -