QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386729 | #5102. Dungeon Crawler | ckiseki | WA | 1ms | 5744kb | C++20 | 3.2kb | 2024-04-11 19:41:07 | 2024-04-11 19:41:07 |
Judging History
answer
#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
constexpr int N = 2000 + 5;
constexpr int Q = 200000 + 5;
vector<pair<int, int>> g[N];
int64_t ans[Q];
vector<tuple<int, int, int>> que[Q];
int pa[N];
int64_t dep[N];
int64_t maxdep[N];
int64_t ex[N];
int tl[N], tr[N], tc;
bool anc(int u, int v) {
return tl[u] <= tl[v] and tr[v] <= tr[u];
}
struct Bests {
pair<int64_t, int> v[3];
int s;
Bests() : s{0} {}
void add(pair<int64_t, int> x) {
v[s++] = x;
sort(v, v + s, greater());
s = min(s, 2);
}
span<pair<int64_t, int>> vals() { return {v, v + s}; };
};
void dfs(int u, int f) {
tl[u] = tc++;
pa[u] = f;
maxdep[u] = 0;
Bests bs;
for (auto [v, w] : g[u]) {
if (v == f)
continue;
dep[v] = dep[u] + w;
dfs(v, u);
maxdep[u] = max(maxdep[u], maxdep[v] + w);
bs.add({maxdep[v] + w, v});
ex[v] = 0;
}
for (auto [v, w] : g[u]) {
if (v == f)
continue;
for (auto [r, o] : bs.vals()) {
if (o == v)
continue;
ex[v] = r + dep[u];
break;
}
}
tr[u] = tc;
}
constexpr int64_t INF = 1LL << 60;
void solve(int n, int s) {
tc = 0;
dep[s] = 0;
dfs(s, s);
for (int i = 0; i < n; ++i) {
maxdep[i] += dep[i];
}
for (auto [k, t, i] : que[s]) {
int64_t best = -INF;
int o = t;
while (not anc(o, k))
o = pa[o];
if (o == t) {
ans[i] = -INF;
continue;
}
if (not anc(t, k)) {
int tp = t;
while (not anc(tp, k)) {
if (anc(pa[tp], k)) {
best = max(best, maxdep[tp]);
break;
}
tp = pa[tp];
}
}
int kp = k;
while (kp != o) {
int64_t cur = maxdep[kp] - 2 * (dep[kp] - dep[o]);
debug(cur);
debug(s, kp, o, maxdep[kp], dep[kp], dep[o]);
best = max(best, cur);
kp = pa[kp];
}
while (pa[o] != s) {
debug(o, ex[o]);
best = max(best, ex[o]);
o = pa[o];
}
ans[i] = best;
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
int64_t tot = 0;
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
tot += w;
}
for (int i = 0; i < q; ++i) {
int s, k, t;
cin >> s >> k >> t;
--s, --k, --t;
que[s].emplace_back(k, t, i);
}
for (int i = 0; i < n; ++i) {
solve(n, i);
// break;
}
for (int i = 0; i < q; ++i) {
if (ans[i] == -INF) {
cout << "impossible\n";
} else {
debug(ans[i]);
cout << 2 * tot - ans[i] << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5744kb
input:
22 5 1 2 7 2 3 5 3 4 8 3 6 6 3 7 3 2 5 6 5 8 2 8 9 11 2 10 16 1 11 12 11 12 4 11 13 9 1 14 25 14 15 4 15 16 5 15 17 6 15 18 1 15 19 8 14 20 7 20 21 9 20 22 17 1 19 9 1 9 19 1 8 9 1 9 8 2 22 11
output:
316 293 316 impossible 314
result:
wrong answer 3rd lines differ - expected: '293', found: '316'