oj.uz

Submission #749126

# Submission time Handle Problem Language Result Execution time Memory
749126 2023-05-27T11:26:24 Z marvinthang Cyberland (APIO23_cyberland) C++17
100 / 100
 2764 ms 401156 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif
 
template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

// end of template

const int MAX = 1e5 + 5;
const double INF = 1e15;
const double EPS = 1e-9;

vector <pair <int, int>> adj[MAX];

double solve(int N, int M, int K, int H, vector <int> x, vector <int> y, vector <int> c, vector <int> arr) {
    REP(i, N) adj[i].clear();
    K = min(K, 70);
    REP(i, M) {
        adj[x[i]].emplace_back(c[i], y[i]);
        adj[y[i]].emplace_back(c[i], x[i]);
    }
    vector <bool> visited(N);
    queue <int> q;
    q.emplace(0);
    visited[0] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [w, v]: adj[u]) if (!visited[v] && v != H) {
            visited[v] = true;
            q.emplace(v);
        }
    }
    vector <vector <vector <double>>> dp(N, vector<vector<double>>(K + 1, vector<double>(2, INF)));
    REP(i, N) if (visited[i] && (!i || !arr[i])) dp[i][0][0] = 0;
    REP(t, K + 1) {
        priority_queue <pair <double, int>, vector <pair <double, int>>, greater <pair <double, int>>> pq;
        REP(u, N) if (dp[u][t][0] < INF - EPS) {
            for (auto [c, v]: adj[u]) if (dp[v][t][1] > dp[u][t][0] + c - EPS) 
                pq.emplace(dp[v][t][1] = dp[u][t][0] + c, v);
        }
        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (u == H || abs(du - dp[u][t][1]) > EPS) continue;
            for (auto [c, v]: adj[u]) if (dp[v][t][1] > dp[u][t][1] + c - EPS) pq.emplace(dp[v][t][1] = dp[u][t][1] + c, v);
        }
        if (t < K) REP(i, N) if (arr[i] == 2 && dp[i][t][1] < INF - EPS) dp[i][t + 1][0] = dp[i][t][1] / 2;
    }
    double res = INF;
    REP(i, K + 1) minimize(res, min(dp[H][i][0], dp[H][i][1]));
    return res < INF - EPS ? res : -1;
}

#ifdef LOCAL
#include <cassert>
#include <cstdio>

#include <vector>

int main() {
    file("cyberland");
  int T;
  assert(1 == scanf("%d", &T));
  while (T--){
    int N,M,K,H;
    assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
    std::vector<int> x(M);
    std::vector<int> y(M);
    std::vector<int> c(M);
    std::vector<int> arr(N);
    for (int i=0;i<N;i++)
      assert(1 == scanf("%d", &arr[i]));
    for (int i=0;i<M;i++)
      assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
  }
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2804 KB Correct.
2 Correct 64 ms 2696 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 4428 KB Correct.
2 Correct 110 ms 4496 KB Correct.
3 Correct 100 ms 4452 KB Correct.
4 Correct 104 ms 4464 KB Correct.
5 Correct 103 ms 4444 KB Correct.
6 Correct 105 ms 20292 KB Correct.
7 Correct 136 ms 19892 KB Correct.
8 Correct 65 ms 37836 KB Correct.
9 Correct 105 ms 2904 KB Correct.
10 Correct 98 ms 2884 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 4436 KB Correct.
2 Correct 103 ms 4512 KB Correct.
3 Correct 100 ms 4424 KB Correct.
4 Correct 114 ms 2892 KB Correct.
5 Correct 107 ms 2880 KB Correct.
6 Correct 30 ms 17364 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 107556 KB Correct.
2 Correct 196 ms 4436 KB Correct.
3 Correct 179 ms 4580 KB Correct.
4 Correct 187 ms 4408 KB Correct.
5 Correct 150 ms 3028 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 4468 KB Correct.
2 Correct 104 ms 4520 KB Correct.
3 Correct 97 ms 4520 KB Correct.
4 Correct 120 ms 20080 KB Correct.
5 Correct 100 ms 2888 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 4576 KB Correct.
2 Correct 117 ms 4392 KB Correct.
3 Correct 228 ms 138512 KB Correct.
4 Correct 98 ms 14548 KB Correct.
5 Correct 103 ms 2848 KB Correct.
6 Correct 92 ms 4576 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 4460 KB Correct.
2 Correct 29 ms 5608 KB Correct.
3 Correct 1051 ms 106800 KB Correct.
4 Correct 496 ms 30992 KB Correct.
5 Correct 1165 ms 70288 KB Correct.
6 Correct 355 ms 24976 KB Correct.
7 Correct 421 ms 29724 KB Correct.
8 Correct 296 ms 7632 KB Correct.
9 Correct 186 ms 4468 KB Correct.
10 Correct 187 ms 4452 KB Correct.
11 Correct 280 ms 4596 KB Correct.
12 Correct 212 ms 4444 KB Correct.
13 Correct 201 ms 4396 KB Correct.
14 Correct 480 ms 25672 KB Correct.
15 Correct 339 ms 12828 KB Correct.
16 Correct 195 ms 4564 KB Correct.
17 Correct 224 ms 4540 KB Correct.
18 Correct 222 ms 4476 KB Correct.
19 Correct 527 ms 4640 KB Correct.
20 Correct 14 ms 2772 KB Correct.
21 Correct 19 ms 4308 KB Correct.
22 Correct 21 ms 4564 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 6820 KB Correct.
2 Correct 60 ms 9280 KB Correct.
3 Correct 1344 ms 401156 KB Correct.
4 Correct 451 ms 18148 KB Correct.
5 Correct 2764 ms 148320 KB Correct.
6 Correct 842 ms 47556 KB Correct.
7 Correct 901 ms 75212 KB Correct.
8 Correct 404 ms 8228 KB Correct.
9 Correct 390 ms 6668 KB Correct.
10 Correct 388 ms 6544 KB Correct.
11 Correct 404 ms 2972 KB Correct.
12 Correct 439 ms 6740 KB Correct.
13 Correct 413 ms 6792 KB Correct.
14 Correct 2416 ms 155976 KB Correct.
15 Correct 2180 ms 199248 KB Correct.
16 Correct 787 ms 68288 KB Correct.
17 Correct 435 ms 16836 KB Correct.
18 Correct 399 ms 6744 KB Correct.
19 Correct 453 ms 6704 KB Correct.
20 Correct 446 ms 6652 KB Correct.
21 Correct 1139 ms 6688 KB Correct.
22 Correct 29 ms 3060 KB Correct.
23 Correct 36 ms 6456 KB Correct.
24 Correct 43 ms 6484 KB Correct.