oj.uz

Submission #754950

# Submission time Handle Problem Language Result Execution time Memory
754950 2023-06-09T04:36:40 Z Zanite Cyberland (APIO23_cyberland) C++17
100 / 100
 1507 ms 11476 KB 
#include "cyberland.h"
// 赤コーダーになりたい
// お願い いいですか？

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si	= short int;
using ll	= long long;
using lll	= __int128;
using ld	= long double;

// Pairs
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pll	= pair<ll, ll>;
using plll	= pair<lll, lll>;
using pld	= pair<ld, ld>;
#define fi	first
#define se	second

// For
#define Frue(i, n, N)		for (int i = (n); i <= (N); i++)
#define  Fru(i, n, N)		for (int i = (n); i <  (N); i++)
#define Frde(i, n, N)		for (int i = (n); i >= (N); i--)
#define  Frd(i, n, N)		for (int i = (n); i >  (N); i--)

// PBDS
template<typename Z>
using ordered_set	= tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs
template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
    return os << '(' << p.fi << ',' << p.se << ')';
}
template<typename Z> ostream& operator<<(ostream &os, const vector<Z> &v) {
    os << '{'; bool _first = 1;
    for (auto &i : v) {if (!_first) os << ", "; os << i; _first = 0;}
    return os << '}';
}
template<typename Z, unsigned long long sz> ostream& operator<<(ostream &os, const array<Z, sz> &arr) {
    os << '{'; bool _first = 1;
    for (auto &i : arr) {if (!_first) os << ", "; os << i; _first = 0;}
    return os << '}';
}

// Quick macro functions
#define sqr(x)			((x)*(x))
#define debug(x)		cout << #x << " = " << (x) << '\n'
#define debugV(v, x)	cout << #v << "[" << (x) << "] = " << (v[x]) << '\n'
#define rrebug(x)		cerr << #x << " = " << (x) << '\n'
#define rrebugV(v, x)	cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n'

#define All(x)			x.begin(), x.end()
#define Sort(x)			sort(All(x))
#define Reverse(x)		reverse(All(x))
#define Uniqueify(x)	Sort(x); x.erase(unique(All(x)), x.end())

#define RandomSeed			chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases	int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Check min and max
template<typename Z> void chmin(Z &a, Z b) {a = min(a, b);}
template<typename Z> void chmax(Z &a, Z b) {a = max(a, b);}
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
    int v;
    ModInt() : v(0) {}
    ModInt(long long _v) {
        v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
        if (v < 0) v += MOD;
    }
 
    friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;}
    friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;}
    friend bool operator< (const ModInt &a, const ModInt &b) {return a.v <  b.v;}
    friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;}
    friend bool operator> (const ModInt &a, const ModInt &b) {return a.v >  b.v;}
    friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;}
 
    ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;}
    ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;}
    ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;}
    ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);}
 
    friend ModInt pow(ModInt a, long long x) {
        ModInt res = 1;
        for (; x; x /= 2, a *= a) if (x & 1) res *= a;
        return res;
    }
    friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);}
 
    ModInt operator+ () const {return ModInt( v);}
    ModInt operator- () const {return ModInt(-v);}
    ModInt operator++() const {return *this += 1;}
    ModInt operator--() const {return *this -= 1;}
 
    friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;}
    friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;}
    friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;}
    friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;}
 
    friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;}
    friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;}
};
const int ModA	= 998244353;
const int ModC	= 1e9 + 7;
using MintA	= ModInt<ModA>;
using MintC	= ModInt<ModC>;

// Other constants
const double INF	= 1e18;
const double iINF	= 1e9;
const double EPS	= 1e-9;
const double iEPS	= 1e-6;

const bool ge(double x, double y) {return ((x - y) >= EPS);}
const bool geq(double x, double y) {return ((x - y) >= -EPS);}

using pdi = pair<double, int>;
void Dijkstra(int N, vector<vector<pii>> &adj, vector<int> &start, vector<double> &dist) {
    priority_queue<pdi, vector<pdi>, greater<pdi>> PQ;
    vector<bool> vis(N, false);
    for (auto i : start) PQ.push({dist[i], i});

    while (!PQ.empty()) {
        auto [cdist, cur] = PQ.top();
        PQ.pop();
        if (vis[cur]) continue;

        // cout << make_pair(cdist, cur) << '\n';

        vis[cur] = true;
        for (auto &[nxt, w] : adj[cur]) {
            if (ge(dist[nxt], dist[cur] + w)) {
                dist[nxt] = dist[cur] + w;
                PQ.push({dist[nxt], nxt});
            }
        }
        // debug(dist);
    }
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    K = min(K, 100);

    vector<vector<pii>> adj(N, vector<pii>());
    for (int i = 0; i < M; i++) {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }
    adj[H].clear();

    vector<int> stReach = {0};
    vector<double> rd(N, INF);
    rd[0] = 0;
    Dijkstra(N, adj, stReach, rd);

    vector<bool> reach(N, false);
    for (int i = 0; i < N; i++) {
        if (geq(rd[i], INF)) continue;
        reach[i] = true;
    }

    vector<int> stInit = {0}, stDiv = {};
    for (int i = 1; i < N; i++) {
        if (arr[i] == 0 && reach[i]) stInit.push_back(i);
        if (arr[i] == 2 && reach[i]) stDiv.push_back(i);
    }

    vector<double> dist(N, INF);
    for (auto i : stInit) dist[i] = 0;

    // K = 0
    Dijkstra(N, adj, stInit, dist);
    double ans = dist[H];
    // debug(dist);

    for (int i = 1; i <= K; i++) {
        vector<double> nd(N, INF);
        vector<int> curSt;
        for (auto i : stDiv) {
            if (geq(dist[i], INF)) continue;
            double cur = dist[i] / 2;
            // debug(cur);
            for (auto &[nxt, w] : adj[i]) {
                nd[nxt] = min(nd[nxt], cur + w);
                curSt.push_back(nxt);
            }
        }
        swap(nd, dist);
        Uniqueify(curSt);

        Dijkstra(N, adj, curSt, dist);
        ans = min(ans, dist[H]);
        // debug(dist);
    }

    if (geq(ans, INF)) ans = -1;
    return ans;
}

#ifdef Zanite
int main() {
  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 40 ms 436 KB Correct.
2 Correct 41 ms 412 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 468 KB Correct.
2 Correct 37 ms 548 KB Correct.
3 Correct 29 ms 468 KB Correct.
4 Correct 30 ms 452 KB Correct.
5 Correct 35 ms 460 KB Correct.
6 Correct 26 ms 1412 KB Correct.
7 Correct 36 ms 1432 KB Correct.
8 Correct 20 ms 2644 KB Correct.
9 Correct 33 ms 400 KB Correct.
10 Correct 31 ms 416 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 464 KB Correct.
2 Correct 36 ms 448 KB Correct.
3 Correct 31 ms 488 KB Correct.
4 Correct 34 ms 340 KB Correct.
5 Correct 32 ms 404 KB Correct.
6 Correct 6 ms 1408 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 7100 KB Correct.
2 Correct 117 ms 448 KB Correct.
3 Correct 104 ms 524 KB Correct.
4 Correct 116 ms 424 KB Correct.
5 Correct 74 ms 392 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 468 KB Correct.
2 Correct 31 ms 436 KB Correct.
3 Correct 29 ms 468 KB Correct.
4 Correct 27 ms 1236 KB Correct.
5 Correct 27 ms 420 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 440 KB Correct.
2 Correct 24 ms 500 KB Correct.
3 Correct 42 ms 9020 KB Correct.
4 Correct 17 ms 1208 KB Correct.
5 Correct 39 ms 408 KB Correct.
6 Correct 30 ms 468 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 476 KB Correct.
2 Correct 21 ms 468 KB Correct.
3 Correct 519 ms 11476 KB Correct.
4 Correct 257 ms 2740 KB Correct.
5 Correct 488 ms 7936 KB Correct.
6 Correct 246 ms 5412 KB Correct.
7 Correct 245 ms 2960 KB Correct.
8 Correct 226 ms 760 KB Correct.
9 Correct 113 ms 420 KB Correct.
10 Correct 111 ms 480 KB Correct.
11 Correct 198 ms 676 KB Correct.
12 Correct 125 ms 400 KB Correct.
13 Correct 121 ms 496 KB Correct.
14 Correct 257 ms 5900 KB Correct.
15 Correct 225 ms 1724 KB Correct.
16 Correct 120 ms 400 KB Correct.
17 Correct 155 ms 468 KB Correct.
18 Correct 136 ms 460 KB Correct.
19 Correct 367 ms 444 KB Correct.
20 Correct 8 ms 380 KB Correct.
21 Correct 10 ms 340 KB Correct.
22 Correct 21 ms 852 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 548 KB Correct.
2 Correct 58 ms 468 KB Correct.
3 Correct 301 ms 11288 KB Correct.
4 Correct 312 ms 996 KB Correct.
5 Correct 1507 ms 7972 KB Correct.
6 Correct 775 ms 5612 KB Correct.
7 Correct 617 ms 4768 KB Correct.
8 Correct 289 ms 668 KB Correct.
9 Correct 294 ms 548 KB Correct.
10 Correct 297 ms 560 KB Correct.
11 Correct 372 ms 456 KB Correct.
12 Correct 323 ms 764 KB Correct.
13 Correct 312 ms 496 KB Correct.
14 Correct 1407 ms 6736 KB Correct.
15 Correct 1092 ms 6052 KB Correct.
16 Correct 430 ms 2380 KB Correct.
17 Correct 312 ms 936 KB Correct.
18 Correct 322 ms 404 KB Correct.
19 Correct 362 ms 420 KB Correct.
20 Correct 347 ms 516 KB Correct.
21 Correct 1016 ms 444 KB Correct.
22 Correct 16 ms 340 KB Correct.
23 Correct 22 ms 388 KB Correct.
24 Correct 54 ms 852 KB Correct.