QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386748 | #5102. Dungeon Crawler | ckiseki | WA | 1ms | 5840kb | C++20 | 3.2kb | 2024-04-11 19:49:52 | 2024-04-11 19:49:52 |
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 (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: 100
Accepted
time: 1ms
memory: 5748kb
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 293 impossible 314
result:
ok 5 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5840kb
input:
100 100 1 2 289384 2 3 930887 2 4 692778 4 5 636916 4 6 747794 4 7 238336 4 8 885387 8 9 760493 8 10 516650 8 11 641422 8 12 202363 8 13 490028 8 14 368691 8 15 520060 8 16 897764 16 17 513927 16 18 180541 16 19 383427 16 20 89173 16 21 455737 16 22 5212 16 23 595369 16 24 702568 16 25 956430 16 26 ...
output:
103526917 103484292 105633958 107777494 104883458 104775512 105434682 107735332 108065173 105371370 104677980 104175650 105887913 105925110 103971939 105376499 105223283 104153426 105082245 105413188 108192116 104800548 104952840 104138329 107167151 104428894 106985688 104385328 104530012 105460460 ...
result:
wrong answer 3rd lines differ - expected: '106288816', found: '105633958'