QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380213 | #5102. Dungeon Crawler | UFRJ# | WA | 1ms | 3580kb | C++20 | 2.3kb | 2024-04-06 21:50:31 | 2024-04-06 21:50:32 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q; cin>>n>>q;
using pii = pair<int64_t, int>;
vector<vector<pii>> g(n);
for(int e = 0; e < n-1; e++){
int u, v;
int64_t w;
cin>>u>>v>>w;
u--, v--;
g[u].emplace_back(w, v);
g[v].emplace_back(w, u);
}
// for(int a =0; a<n; a++){
// for(int b =0; b<n; b++){
// cout<<a+1<<" "<<b+1<<" "<<is_ancestor(a,b)<<"\n";
// }
// }
vector<vector<int64_t>> sum_edges(n, vector<int64_t>(n));
vector<vector<int64_t>> farthest(n, vector<int64_t>(n));
vector<vector<int>> parent(n, vector<int>(n));
vector<vector<int64_t>> dist(n, vector<int64_t>(n));
for(int r = 0; r < n; r++){
auto dfs = [&](const int trap_child, int64_t &frt, int u, int p, int64_t accum, auto &&self) -> int64_t {
parent[r][u] = trap_child;
dist[r][u] = accum;
frt = max(frt, dist[r][u]);
int64_t sum = 0;
for(auto [w, v] : g[u]) if(v != p){
sum += w + self(trap_child, frt, v, u, accum + w, self);
}
return sum;
};
for(auto [w, child] : g[r]){
sum_edges[r][child] = w + dfs(child, farthest[r][child], child, r, w, dfs);
}
// for(auto [w, child] : g[r]){
// cout<<r+1<<" --> "<<child+1<<" : \n";
// cout<<" "<<sum_edges[r][child]<<" "<<farthest[r][child]<<" \n";
// }
}
for(int i =0; i < q; i++){
int start, key, trap;
cin>>start>>key>>trap;
start--, key--, trap--;
if(parent[trap][start] != parent[trap][key]){
cout<<"impossible\n";
continue;
}
int64_t answer = 0;
int p_start = parent[trap][start];
answer += sum_edges[trap][p_start] * 2 - dist[trap][start];
int64_t farthest_child = 0;
for(auto [w, child] : g[trap]){
if(child == p_start) continue;
farthest_child = max(farthest_child, farthest[trap][child]);
answer += sum_edges[trap][child] * 2;
}
answer -= farthest_child;
cout<<answer<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3580kb
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 305 316 impossible 314
result:
wrong answer 2nd lines differ - expected: '293', found: '305'