oj.uz

Submission #485264

# Submission time Handle Problem Language Result Execution time Memory
485264 2021-11-06T19:51:42 Z xiaowuc1 None (KOI16_gas) C++17
100 / 100
 799 ms 708 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<pii> gasprices(n);
  for(int i = 0; i < n; i++) {
    int x;
    cin >> x;
    gasprices[i] = {x, i};
  }
  sort(all(gasprices));
  vector<vector<pii>> edges(n);
  while(m--) {
    int a, b, w;
    cin >> a >> b >> w;
    a--; b--;
    edges[a].eb(b, w);
    edges[b].eb(a, w);
  }
  vector<ll> cost(n, 1e18);
  cost[0] = 0;
  while(sz(gasprices)) {
    auto [currp, src] = gasprices.back(); gasprices.pop_back();
    vector<int> dp(n, 2e9);
    dp[src] = 0;
    priority_queue<pii> q;
    q.emplace(-dp[src], src);
    while(sz(q)) {
      auto [w, v] = q.top(); q.pop();
      w *= -1;
      if(dp[v] != w) continue;
      for(auto [nv, gain]: edges[v]) {
        if(dp[v] + gain < dp[nv]) {
          dp[nv] = dp[v] + gain;
          q.emplace(-dp[nv], nv);
        }
      }
    }
    for(int i = 0; i < n; i++) {
      cost[i] = min(cost[i], cost[src] + dp[i] * (ll)currp);
    }
  }
  cout << cost[n-1] << "\n";
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 460 KB Output is correct
2 Correct 152 ms 524 KB Output is correct
3 Correct 147 ms 512 KB Output is correct
4 Correct 146 ms 460 KB Output is correct
5 Correct 147 ms 536 KB Output is correct
6 Correct 145 ms 460 KB Output is correct
7 Correct 153 ms 460 KB Output is correct
8 Correct 138 ms 460 KB Output is correct
9 Correct 136 ms 528 KB Output is correct
10 Correct 136 ms 460 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 528 KB Output is correct
2 Correct 655 ms 588 KB Output is correct
3 Correct 667 ms 588 KB Output is correct
4 Correct 657 ms 708 KB Output is correct
5 Correct 655 ms 632 KB Output is correct
6 Correct 795 ms 656 KB Output is correct
7 Correct 796 ms 708 KB Output is correct
8 Correct 799 ms 632 KB Output is correct
9 Correct 662 ms 596 KB Output is correct
10 Correct 662 ms 604 KB Output is correct
11 Correct 659 ms 596 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 8 ms 356 KB Output is correct
15 Correct 9 ms 316 KB Output is correct
16 Correct 7 ms 332 KB Output is correct
17 Correct 46 ms 332 KB Output is correct
18 Correct 48 ms 424 KB Output is correct
19 Correct 20 ms 372 KB Output is correct
20 Correct 19 ms 332 KB Output is correct
21 Correct 22 ms 332 KB Output is correct
22 Correct 20 ms 372 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 151 ms 460 KB Output is correct
15 Correct 152 ms 524 KB Output is correct
16 Correct 147 ms 512 KB Output is correct
17 Correct 146 ms 460 KB Output is correct
18 Correct 147 ms 536 KB Output is correct
19 Correct 145 ms 460 KB Output is correct
20 Correct 153 ms 460 KB Output is correct
21 Correct 138 ms 460 KB Output is correct
22 Correct 136 ms 528 KB Output is correct
23 Correct 136 ms 460 KB Output is correct
24 Correct 148 ms 528 KB Output is correct
25 Correct 655 ms 588 KB Output is correct
26 Correct 667 ms 588 KB Output is correct
27 Correct 657 ms 708 KB Output is correct
28 Correct 655 ms 632 KB Output is correct
29 Correct 795 ms 656 KB Output is correct
30 Correct 796 ms 708 KB Output is correct
31 Correct 799 ms 632 KB Output is correct
32 Correct 662 ms 596 KB Output is correct
33 Correct 662 ms 604 KB Output is correct
34 Correct 659 ms 596 KB Output is correct
35 Correct 8 ms 356 KB Output is correct
36 Correct 9 ms 316 KB Output is correct
37 Correct 7 ms 332 KB Output is correct
38 Correct 46 ms 332 KB Output is correct
39 Correct 48 ms 424 KB Output is correct
40 Correct 20 ms 372 KB Output is correct
41 Correct 19 ms 332 KB Output is correct
42 Correct 22 ms 332 KB Output is correct
43 Correct 20 ms 372 KB Output is correct
44 Correct 191 ms 524 KB Output is correct
45 Correct 299 ms 460 KB Output is correct
46 Correct 325 ms 536 KB Output is correct
47 Correct 674 ms 636 KB Output is correct
48 Correct 657 ms 632 KB Output is correct
49 Correct 572 ms 588 KB Output is correct
50 Correct 571 ms 708 KB Output is correct
51 Correct 584 ms 596 KB Output is correct
52 Correct 572 ms 588 KB Output is correct