QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560106 | #5102. Dungeon Crawler | Rico64 | WA | 0ms | 3720kb | C++23 | 3.8kb | 2024-09-12 12:38:00 | 2024-09-12 12:38:00 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,long long>> graph[2000];
int parent[2000][11], depth[2000];
void search0(int v) {
for (const auto& e : graph[v]) {
if (e.first == parent[v][0]) continue;
parent[e.first][0] = v;
for (int i = 1; i < 11; ++i) {
if (parent[e.first][i-1] == -1) {
parent[e.first][i] = -1;
} else {
parent[e.first][i] = parent[parent[e.first][i-1]][i-1];
}
}
depth[e.first] = depth[v] + 1;
search0(e.first);
}
}
long long subpath[2000];
void search1(int v) {
subpath[v] = 0;
for (const auto& e : graph[v]) {
if (e.first == parent[v][0]) continue;
search1(e.first);
subpath[v] = max(subpath[v], subpath[e.first] + e.second);
}
}
long long topdp[2000];
void search2(int v, long long cs) {
int n = graph[v].size();
long long ress[n];
fill(ress, ress + n, 0);
for (int i = 0; i < n; ++i) {
const auto& e = graph[v][i];
if (e.first == parent[v][0]) continue;
ress[i] = subpath[e.first] + e.second + cs;
search2(e.first, cs + e.second);
}
long long pmax[n], smax[n];
for (long long i = 0, p = 0; i < n; ++i) p = pmax[i] = max(ress[i], p);
for (long long i = n - 1, p = 0; i >= 0; --i) p = smax[i] = max(ress[i], p);
for (int i = 0; i < n; ++i) {
const auto& e = graph[v][i];
if (e.first == parent[v][0]) continue;
topdp[e.first] = max(i == 0 ? 0 : pmax[i - 1], i == n - 1 ? 0 : smax[i + 1]);
}
}
int up(int a, int l) {
for (int i = 10; i >= 0; --i) {
if ((l >> i & 1) == 1 && a >= 0) {
a = parent[a][i];
}
}
return a;
}
int lca(int a, int b) {
if (depth[a] > depth[b]) a = up(a, depth[a] - depth[b]);
if (depth[b] > depth[a]) b = up(b, depth[b] - depth[a]);
if (a == b) return a;
for (int i = 10; i >= 0; --i) {
if (parent[a][i] != parent[b][i]) {
a = parent[a][i];
b = parent[b][i];
}
}
a = parent[a][0];
return a;
}
int main() {
int n, ql;
cin >> n >> ql;
long long csm = 0;
for (int i = 1, f, t, c; i < n; ++i) {
cin >> f >> t >> c;
f--; t--;
graph[f].push_back({t, c});
graph[t].push_back({f, c});
csm += c;
}
pair<int,pair<int,pair<int,int>>> qs[ql];
for (int qi = 0; qi < ql; ++qi) {
cin >> qs[qi].first >> qs[qi].second.first >> qs[qi].second.second.first;
qs[qi].second.second.second = qi;
}
sort(qs, qs + ql);
long long res[ql];
for (int qi = 0, ps = -1; qi < ql; ++qi) {
int s = qs[qi].first, k = qs[qi].second.first, t = qs[qi].second.second.first;
s--; t--; k--;
int ii = qs[qi].second.second.second;
if (ps != s) {
fill(parent[s], parent[s] + 11, -1);
depth[s] = 0;
search0(s);
ps = s;
search1(s);
topdp[s] = 0;
search2(s, 0);
// cout << s << " : " << endl;
// for (int i = 0; i < n; ++i) cout << subpath[i] << ' '; cout << endl;
// for (int i = 0; i < n; ++i) cout << topdp[i] << ' '; cout << endl;
}
int o = lca(k, t);
if (o == t) {
res[ii] = -10000;
} else if (o == k) {
res[ii] = csm * 2L - subpath[s];
} else {
int no = up(k, depth[k] - depth[o] - 1);
res[ii] = csm * 2L - topdp[no];
}
}
for (int qi = 0; qi < ql; ++qi) {
if (res[qi] == -10000) {
cout << "impossible" << endl;
} else {
cout << res[qi] << endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3720kb
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: 0ms
memory: 3580kb
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 106288816 104379596 104405611 107219240 106850550 105291604 103838430 106026228 107121708 106619378 105894571 104509242 103971939 106792367 105223283 104153426 106498113 106829056 104130613 106216416 106846555 104138329 103769253 106879186 104044745 104385328 106973740 106876328 ...
result:
wrong answer 6th lines differ - expected: '104775512', found: '107219240'