| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 983101 | vjudge1 | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
int nonol(vector<vector<pair<int, int>>> g, int N, int M, int K, int H, vector<int> arr) {
vector<bool> used(N), ot(N);
function<void(int, int)> dfs = [&](int v, int cnt) {
assert(!used[v]);
used[v] = true;
for (auto [to, weight]: g[v]) {
if (!used[to]) {
if (arr[to] == 2 && cnt) {
ot[to] = true;
dfs(to, cnt - 1);
} else dfs(to, cnt);
}
}
};
vector<double> d(N + 1, 1e18);
d[0] = 0;
set<pair<double, int>> q;
q.emplace(d[0], 0);
while (!q.empty()) {
int nearest = q.begin()->second;
q.erase(q.begin());
for (auto [to, weight]: g[nearest]) {
double dis = d[nearest] + weight;
if (ot[to]) dis /= 2;
if (!arr[to]) dis = 0;
if (d[to] > dis) {
q.erase(pair{d[to], to});
d[to] = dis;
q.emplace(d[to], to);
}
}
}
if (d[H] == 1e18) d[H] = -1;
return d[H];
}
int s1(vector<vector<pair<int, int>>> g, int N, int M, int K, int H, vector<int> arr) {
int dis = 1e18;
bool can = false;
int zap, u;
for (auto [to, weight]: g[0]) {
if (to == H) {
dis = min(dis, weight);
} else can = true, zap = weight, u = to;
}
if (can) {
int sec, w;
can = false;
for (auto [to, weight]: g[u]) {
if (to == H) sec = to, can = false, w = weight;
}
if (arr[u] == 0) dis = min(dis, w);
else if (arr[u] == 1) dis = min(dis, w + zap);
else dis = min(dis, zap / 2 + w);
}
if (dis == 1e18) dis = -1;
return dis;
}
int s4(vector<vector<pair<int, int>>> g, int N, int M, int K, int H, vector<int> arr);
int yesnol(vector<vector<pair<int, int>>> g, int N, int M, int K, int H, vector<int> arr);
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) {
vector<vector<pair<int, int>>> g(N);
bool is2 = true;
for (int i = 0; i < M; ++i) {
g[x[i]].emplace_back(y[i], c[i]);
g[y[i]].emplace_back(x[i], c[i]);
if (x[i] != i || y[i] != i + 1) is2 = false;
}
if (N <= 3) return s1(g, N, M, K, H, arr);
else if (is2) return s4(g, N, M, K, H, arr);
else if (find(arr.begin(), arr.end(), 0LL) == arr.end()) return nonol(g, N, M, K, H, arr);
else return yesnol(g, N, M, K, H, arr);
}