제출 #754950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
754950		Zanite	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	1507 ms	11476 KiB

cyberland

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3