QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91180 | #5102. Dungeon Crawler | _skb_ | WA | 1ms | 5668kb | C++17 | 4.2kb | 2023-03-27 16:42:39 | 2023-03-27 16:42:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
struct debug {
#define contPrint { *this << "["; \
int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
*this << "]"; return *this;}
~debug(){cerr << endl;}
template<class c> debug& operator<<(c x) {cerr << x; return *this;}
template<class c, class d>
debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")";
return *this;}
template<class c> debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};
#define dbg(x) "[" << #x << ": " << x << "] "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() <<
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
const int N = 2002;
vector<pair<int, int>> G[N];
int max_path[N][N];
i64 max_path_cost[N][N][2];
int edge_cost[N][N];
int P[N][N];
i64 dfs(int cur, int root, int p)
{
i64 mx = 0;
i64 mx2 = 0;
i64 which = -1;
P[root][cur] = p;
for(auto it : G[cur]) {
if(it.first != p) {
i64 x = dfs(it.first, root, cur) + it.second;
if(x > mx) {
mx2 = mx;
mx = x;
which = it.first;
} else if(x == mx) {
mx2 = mx;
}
}
}
max_path[root][cur] = which;
max_path_cost[root][cur][0] = mx;
max_path_cost[root][cur][1] = mx2;
return mx;
}
int main()
{
int n, q;
scanf("%d %d", &n, &q);
i64 tot_cost = 0;
for(int i = 1; i < n; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
G[u].push_back({v, w});
G[v].push_back({u, w});
edge_cost[u][v] = w;
edge_cost[v][u] = w;
tot_cost += w + w;
}
for(int i = 1; i <= n; i++) dfs(i, i, 0);
int stk[N];
int idx = 0;
int vis[N];
memset(vis, 0, sizeof vis);
// Wa() dbg(tot_cost);
while(q--) {
int root, key, trap;
scanf("%d %d %d", &root, &key, &trap);
int cur = key;
while(cur != root) {
stk[idx++] = cur;
vis[cur] = 1;
cur = P[root][cur];
}
stk[idx++] = cur;
vis[cur] = 1;
if(vis[trap]) {
puts("impossible");
} else {
int lca = trap;
while(!vis[lca]) {
lca = P[root][lca];
}
i64 tot = 0;
cur = key;
while(cur != lca) {
tot += edge_cost[cur][P[root][cur]];
cur = P[root][cur];
}
i64 lca_to_root_cost = 0;
cur = lca;
while(cur != root) {
lca_to_root_cost += edge_cost[cur][P[root][cur]];
cur = P[root][cur];
}
i64 ans = 1e18;
cur = key;
int prv = cur;
bool lca_found = false;
if(cur == lca) {
lca_found = true;
}
while(cur != root) {
if(max_path[root][cur] != prv) {
ans = min(ans, tot_cost + tot - max_path_cost[root][cur][0] - lca_to_root_cost);
} else {
ans = min(ans, tot_cost + tot - max_path_cost[root][cur][1] - lca_to_root_cost);
}
prv = cur;
cur = P[root][cur];
if(!lca_found) {
tot -= edge_cost[prv][cur];
} else {
lca_to_root_cost -= edge_cost[prv][cur];
}
if(cur == lca) {
lca_found = true;
}
}
if(max_path[root][cur] != prv) {
ans = min(ans, tot_cost + tot - max_path_cost[root][cur][0] - lca_to_root_cost);
} else {
ans = min(ans, tot_cost + tot - max_path_cost[root][cur][1] - lca_to_root_cost);
}
// Wa() dbg(lca_to_root_cost);
assert(lca_to_root_cost == 0);
printf("%lld\n", ans);
}
while(idx > 0) {
vis[stk[--idx]] = 0;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4000kb
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: 5668kb
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 107245246 104379596 104405611 104775512 105434682 105291604 103838430 105371370 104677980 104175650 105894571 104509242 103971939 105376499 105223283 104153426 105082245 105413188 104130613 104800548 107845726 104138329 103769253 105456754 104044745 104385328 107353400 105460460 ...
result:
wrong answer 3rd lines differ - expected: '106288816', found: '107245246'