QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#90909 | #5102. Dungeon Crawler | _skb_ | WA | 1ms | 3952kb | C++17 | 3.4kb | 2023-03-26 02:38:03 | 2023-03-26 02:38:05 |
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);
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];
}
cur = root;
bool found = false;
while(max_path[root][cur] != -1) {
if(cur == key) found = true;
cur = max_path[root][cur];
}
if(cur == key) found = true;
if(!found || lca == key) {
printf("%lld\n", tot_cost - max_path_cost[root][root][0]);
} else {
i64 ans = 1e18;
i64 cur_sum = 0;
cur = lca;
while(cur != key) {
ans = min(ans, tot_cost + cur_sum - max_path_cost[root][cur][1]);
cur_sum += edge_cost[cur][max_path[root][cur]];
cur = max_path[root][cur];
}
ans = min(ans, tot_cost + cur_sum - max_path_cost[root][cur][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: 0
Wrong Answer
time: 1ms
memory: 3952kb
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:
293 293 293 impossible 321
result:
wrong answer 1st lines differ - expected: '316', found: '293'