Submission #1228136

#TimeUsernameProblemLanguageResultExecution timeMemory
1228136DzadzoCyberland (APIO23_cyberland)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "cyberland.h" using namespace std; // Faster Dijkstra with struct-based priority queue and pruning double solve(int n, int m, int K, int h, const vector<int>& x, const vector<int>& y, const vector<int>& c, const vector<int>& arr) { vector<vector<pair<int,int>>> adj(n); adj.reserve(n); for (int i = 0; i < m; ++i) { adj[x[i]].emplace_back(y[i], c[i]); adj[y[i]].emplace_back(x[i], c[i]); } // Reachability check (BFS) vector<char> reachable(n, 0); deque<int> dq; dq.push_back(0); reachable[0] = 1; while (!dq.empty()) { int u = dq.front(); dq.pop_front(); for (auto& [v, w] : adj[u]) { if (!reachable[v]) { reachable[v] = 1; dq.push_back(v); } } } if (!reachable[h]) return -1; // Determine effective K by counting reachable special nodes int special_count = 0; for (int i = 0; i < n; ++i) if (reachable[i] && arr[i] == 2) ++special_count; int maxK = min(K, special_count); const double INF = 1e15; vector<vector<double>> dist(n, vector<double>(maxK + 1, INF)); struct State { double d; int v, k; bool operator<(State const& o) const { return d > o.d; } }; priority_queue<State> pq; // Multi-source: start at 0 and any arr[i]==0 node auto push_state = [&](int node, int used, double d) { if (d < dist[node][used]) { dist[node][used] = d; pq.push({d, node, used}); } }; push_state(0, 0, 0.0); for (int i = 1; i < n; ++i) { if (reachable[i] && arr[i] == 0) push_state(i, 0, 0.0); } double best = INF; while (!pq.empty()) { auto st = pq.top(); pq.pop(); if (st.d != dist[st.v][st.k]) continue; if (st.d >= best) break; // prune worse paths if (st.v == h) { best = st.d; continue; } for (auto& [to, w] : adj[st.v]) { double nd = st.d + w; push_state(to, st.k, nd); if (arr[to] == 2 && st.k < maxK) { push_state(to, st.k + 1, (st.d + w) * 0.5); } } } return (best < INF ? best : -1); }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc7mscPm.o: in function `main':
grader.cpp:(.text.startup+0x71e): undefined reference to `solve(int, int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status