| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 983101 | vjudge1 | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}