Submission #952684

#	Time	Username	Problem	Language	Result	Execution time	Memory
952684		Pring	Cyberland (APIO23_cyberland)	C++17	68 / 100	3044 ms	13792 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef pair<double, int> pli;

namespace {
    const int MXN = 100005;
    const double INF = 3.9e239, INF_BOUND = 1e18;
    int n, m, k, h;
    vector<int> x, y, c, s;
    vector<pli> edge[MXN], lst;
    vector<pli> sr;
    double dis[MXN], ans;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    bitset<MXN> b;

    void DFS(int id) {
        debug(id);
        b[id] = true;
        if (s[id] == 0) sr.push_back(mp(0.0, id));
        for (auto &[w, i] : edge[id]) {
            if (b[i]) continue;
            DFS(i);
        }
    }

    void DIJKSTRA(bool f = false) {
        fill(dis + 1, dis + n + 1, INF);
        if (f) {
            for (auto &i : sr) pq.push(i);
        } else {
            for (auto &[len, id] : sr) {
                for (auto &[w, i] : edge[id]) {
                    pq.push(mp(len + w, i));
                }
            }
        }
        while (pq.size()) {
            auto [len, id] = pq.top();
            pq.pop();
            if (dis[id] < INF) continue;
            dis[id] = len;
            for (auto &[w, i] : edge[id]) {
                if (dis[i] < INF) continue;
                pq.push(mp(len + w, i));
            }
        }
    }

    double GETANS() {
        double ans = INF;
        for (auto &[w, id] : lst) {
            if (b[id] && s[id] == 2) ans = min(ans, dis[id] / 2 + w);
            else if (b[id]) ans = min(ans, dis[id] + w);
        }
        return ans;
    }

    double miku() {
        FOR(i, 0, m) {
            if (x[i] != h && y[i] != h) {
                edge[x[i]].push_back(mp((double) c[i], y[i]));
                edge[y[i]].push_back(mp((double) c[i], x[i]));
            } else {
                lst.push_back(mp((double) c[i], x[i] ^ y[i] ^ h));
            }
        }
        ans = INF;
        sr.push_back(mp(0.0, 1));
        DFS(1);
        DIJKSTRA(true);
        ans = min(ans, GETANS());
        while (k--) {
            sr.clear();
            FOR(i, 1, n + 1) if (b[i] && s[i] == 2) sr.push_back(mp(dis[i] / 2.0, i));
            DIJKSTRA();
            ans = min(ans, GETANS());
        }
        return ans;
    }

    void RESET() {
        FOR(i, 1, n + 1) {
            edge[i].clear();
            b[i] = false;
        }
        sr.clear();
        lst.clear();
    }
}

double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> S) {
    H++;
    for (auto &i : X) i++;
    for (auto &i : Y) i++;
    S.insert(S.begin(), 0);
    ::n = N;
    ::m = M;
    ::k = K;
    ::h = H;
    ::x = X;
    ::y = Y;
    ::c = C;
    ::s = S;
    double ans = miku();
    RESET();
    return (ans >= ::INF_BOUND ? -1.0 : ans);
}

#ifdef MIKU
int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int n, m, k, h;
    vector<int> x, y, c, s;
    cin >> n >> m >> k >> h;
    x.resize(m);
    y.resize(m);
    c.resize(m);
    s.resize(n);
    for (auto &i : s) cin >> i;
    FOR(i, 0, m) cin >> x[i] >> y[i] >> c[i];
    double d = solve(n, m, k, h, x, y, c, s);
    cout << d << '\n';
    return 0;
}
#endif

Compilation message (stderr)

cyberland.cpp: In function 'void {anonymous}::DFS(int)':
cyberland.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
cyberland.cpp:33:9: note: in expansion of macro 'debug'
   33 |         debug(id);
      |         ^~~~~

• 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: 0 / 29
• Subtask 8: 0 / 3