oj.uz

Submission #472355

# Submission time Handle Problem Language Result Execution time Memory
472355 2021-09-13T12:09:26 Z elgamalsalman Toll (BOI17_toll) C++14
10 / 100
 67 ms 8516 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, dp[50050];
vvii  adj;

void getToll(ll u) {
  //cerr << "// getToll(" << u << ", " << v << ")\n";
  if (dp[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";
    getToll(edge.fi);
    ll currToll = dp[edge.fi] + edge.se;
    if (currToll < minToll) minToll = currToll;
  }

  dp[u] = minToll;
  //cerr << "// " <<  dp[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(dp, -1, sizeof dp);
  dp[0] = 0;
  for (int i = 0; i < n; i++) getToll(i);

  for (ll i = 0; i < o; i++) {
    ll a, b;
    cin >> a >> b;
    cout << (dp[b] >= 1e10 ? -1 : dp[b]) << '\n';
  }
}

Subtask #1
0 / 7.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4412 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 708 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 3 ms 840 KB Output is correct
8 Correct 5 ms 844 KB Output is correct
9 Correct 24 ms 4348 KB Output is correct
10 Correct 65 ms 8060 KB Output is correct
11 Correct 47 ms 6212 KB Output is correct
12 Correct 35 ms 5188 KB Output is correct
13 Correct 67 ms 8516 KB Output is correct
14 Correct 41 ms 5448 KB Output is correct
15 Correct 36 ms 4636 KB Output is correct
16 Correct 35 ms 4628 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #5
0 / 44.0

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