oj.uz

Submission #472358

# Submission time Handle Problem Language Result Execution time Memory
472358 2021-09-13T12:14:57 Z elgamalsalman Toll (BOI17_toll) C++14
10 / 100
 3000 ms 7716 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

ll k, n, m, o, dp1[50050], dp2[50050];
vvii  adj;

void getToll2(ll u, ll v) {
  //cerr << "// getToll(" << u << ", " << v << ")\n";
  if (dp2[u] != -1) return;
  if (u == v) { dp2[u] = 0; return; }
  if (u/k >= v/k) { dp2[u] = 1e10; return; }

  //if (u == 1) cerr << "// check1\n";

  ll minToll = 1e10;
  for (ii edge : adj[u]) {
    //if (u == 1) cerr << "// check2 {" << edge.fi << ", " << edge.se << "}\n";
    getToll2(edge.fi, v);
    if (dp2[edge.fi] >= 1e10) continue;
    ll currToll = dp2[edge.fi] + edge.se;
    if (currToll < minToll) minToll = currToll;
  }

  dp2[u] = minToll;
  //cerr << "// " <<  dp2[u] << '\n';
}

void getToll1(ll u) {
  //cerr << "// getToll(" << u << ", " << v << ")\n";
  if (dp1[u] != -1) return;

  //if (u == 1) cerr << "// check1\n";

  ll minToll = 1e10;
  for (ii edge : adj[u]) {
    //if (u == 1) cerr << "// check2 {" << edge.fi << ", " << edge.se << "}\n";
    getToll1(edge.fi);
    ll currToll = dp1[edge.fi] + edge.se;
    if (currToll < minToll) minToll = currToll;
  }

  dp1[u] = minToll;
  //cerr << "// " <<  dp1[u] << '\n';
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> k >> n >> m >> o;
  adj.assign(n + 20, vii());
  for (ll i = 0; i < m; i++) {
    ll a, b, t;
    cin >> a >> b >> t;
    adj[b].push_back({a, t});
  }

  memset(dp1, -1, sizeof dp1);
  dp1[0] = 0;
  for (int i = 0; i < n; i++) getToll1(i);

  for (ll i = 0; i < o; i++) {
    memset(dp2, -1, sizeof dp2);
    ll a, b;
    cin >> a >> b;
    if (a == 0) {
      cout << (dp1[b] >= 1e10 ? -1 : dp1[b]) << '\n';
    } else {
      getToll2(a, b);
      cout << (dp2[b] >= 1e10 ? -1 : dp2[b]) << '\n';
    }
  }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 7716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 4804 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 144 ms 1152 KB Output is correct
8 Correct 142 ms 1192 KB Output is correct
9 Correct 163 ms 3964 KB Output is correct
10 Correct 220 ms 6236 KB Output is correct
11 Correct 190 ms 4916 KB Output is correct
12 Correct 172 ms 4244 KB Output is correct
13 Correct 107 ms 6464 KB Output is correct
14 Correct 84 ms 4544 KB Output is correct
15 Correct 75 ms 3780 KB Output is correct
16 Correct 72 ms 3704 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 972 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 972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 7716 KB Time limit exceeded
2 Halted 0 ms 0 KB -