oj.uz

Submission #651496

# Submission time Handle Problem Language Result Execution time Memory
651496 2022-10-19T05:56:42 Z alvinpiter Toll (BOI17_toll) C++17
0 / 100
 131 ms 28460 KB 
/*
Picture the nodes are arranged in a 2D matrix with K rows
where each column contains nodes with the same floor(index/K).

dp[node][jump][k] = minimum cost to go from node "node" to the k-th node located in column node/K + 2^jump.
*/

#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXN 50000
#define MAXLG 15
#define MAXK 5

int K, N, M, Q, dp[MAXN + 3][MAXLG + 3][MAXK + 3];

int main() {
  cin >> K >> N >> M >> Q;

  for (int i = 0; i < N; i++) {
    for (int jump = 0; jump <= MAXLG; jump++) {
      for (int k = 0; k <= K; k++) {
        dp[i][jump][k] = INF;
      }
    }
  }

  for (int i = 0; i < M; i++) {
    int a, b, t;
    cin >> a >> b >> t;

    dp[a][0][b%K] = t;
  }

  int numberOfColumns = N/K + (N%K == 0 ? 0 : 1);
  for (int jump = 1; jump <= MAXLG; jump++) {
    for (int i = 0; i < N; i++) {
      int currentColumn = i/K;
      int destinationColumn = currentColumn + (1 << jump);

      if (destinationColumn >= numberOfColumns) {
        continue;
      }

      for (int destinationK = 0; destinationK < K; destinationK++) {
        for (int transitK = 0; transitK < K; transitK++) {
          int transitColumn = currentColumn + (1 << (jump - 1));
          int transitNode = transitColumn * K + transitK;

          dp[i][jump][destinationK] = min(dp[i][jump][destinationK], dp[i][jump - 1][transitK] + dp[transitNode][jump - 1][destinationK]);
        }
      }
    }
  }

  for (int q = 0; q < Q; q++) {
    int a, b;
    cin >> a >> b;

    int currentColumn = a/K, destinationColumn = b/K;
    int columnDiff = destinationColumn - currentColumn;

    map<int, int> currentNodes;
    currentNodes[a] = 0; // The value is dummy

    for (int jump = 0; jump <= MAXLG; jump++) {
      if (columnDiff & (1 << jump)) {
        map<int, int> newNodes;

        for (auto [currentNode, temp]: currentNodes) {
          for (int destinationK = 0; destinationK < K; destinationK++) {
            int destinationColumn = currentColumn + (1 << jump);
            int destinationNode = destinationColumn * K + destinationK;

            if (newNodes.find(destinationNode) == newNodes.end()) {
              newNodes[destinationNode] = dp[currentNode][jump][destinationK];
            } else {
              newNodes[destinationNode] = min(newNodes[destinationNode], dp[currentNode][jump][destinationK]);
            }
          }
        }

        swap(currentNodes, newNodes);
        currentColumn += (1 << jump);
      }
    }

    if (currentNodes.find(b) != currentNodes.end()) {
      cout << currentNodes[b] << endl;
    } else {
      cout << -1 << endl;
    }
  }
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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