이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cyberland.h"
#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <bitset>
using namespace std;
const int MAXN = 1e5 + 123;
const double INF = 1e18 + 177013;
vector<pair<int, int>> edg[MAXN];
bitset<MAXN> used;
void dfs_connect(int v, int H) {
if (used[v])
return;
used[v] = 1;
if (v == H)
return;
for (auto [u, d] : edg[v]) {
dfs_connect(u, H);
}
}
void initialize(int N, int M, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
for (int i = 0; i < N; ++i) {
edg[i].clear();
}
used = 0;
for (int i = 0; i < M; ++i) {
edg[x[i]].push_back({y[i], c[i]});
edg[y[i]].push_back({x[i], c[i]});
}
}
vector<double> bfs(int N, const vector<pair<double, int>>& inits, double mod) {
vector<double> depth(N, INF);
set<pair<double, int>> rdepth;
used = 0;
for (const auto &[d, v] : inits) {
depth[v] = d;
rdepth.insert({d, v});
}
while (rdepth.size()) {
const auto [d, v] = *rdepth.begin();
rdepth.erase(rdepth.begin());
for (auto [u, len] : edg[v]) {
if (d + len * mod < depth[u]) {
rdepth.erase({depth[u], u});
depth[u] = d + len * mod;
rdepth.insert({depth[u], u});
}
}
}
return depth;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
initialize(N, M, x, y, c, arr);
dfs_connect(0, H);
if (!used[H])
return -1;
bitset<MAXN> start;
for (int i = 0; i < N; ++i) {
start[i] = used[i] & (i == 0 || arr[i] == 0);
}
bitset<MAXN> div2;
for (int i = 0; i < N; ++i) {
div2[i] = arr[i] == 2 && used[i];
}
K = min({K, 200});
vector<double> depth;
double ans = INF;
depth = bfs(N, {{0, H}}, 1);
for (int i = start._Find_first(); i < N; i = start._Find_next(i))
ans = min(ans, depth[i]);
for (auto [u, d] : edg[H]) {
edg[u].erase(find(edg[u].begin(), edg[u].end(), pair<int, int>(H, d)));
}
for (int ki = 1; ki <= K; ++ki) {
vector<pair<double, int>> pts;
for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
pts.push_back({depth[i], i});
}
double mod = pow(0.5, ki);
depth = bfs(N, pts, mod);
for (int i = start._Find_first(); i < N; i = start._Find_next(i))
ans = min(ans, depth[i]);
for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
depth[i] = INF;
for (auto [u, d] : edg[i])
depth[i] = min(depth[i], depth[u] + d * mod);
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |