QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#382248 | #5102. Dungeon Crawler | UFRJ | WA | 1ms | 3708kb | C++20 | 3.8kb | 2024-04-08 08:14:37 | 2024-04-08 08:14:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template<typename T, typename Cmp = less<T>>
struct rmq_t : private Cmp{
int N = 0;
vector<vector<T>> table;
const T& min(const T& a, const T &b) const{
return Cmp::operator()(a,b) ? a : b;
}
rmq_t(){}
rmq_t(const vector<T>& values): N(int(values.size())), table(__lg(N)+1){
table[0] = values;
for(int a=1; a < int(table.size()); ++a){
table[a].resize(N - (1<<a) + 1);
for(int b = 0; b + (1<<a) <= N; ++b)
table[a][b] = min(table[a-1][b], table[a-1][b+(1<<(a-1))]);
}
}
T query(int a, int b) const {
int lg = __lg(b-a);
return min(table[lg][a], table[lg][b-(1<<lg)]);
}
};
struct lca_t{
int N = 0;
vector<vector<pair<int64_t, int>>> g;
vector<int> in, out, par;
vector<int64_t> prof, max_prof;
vector<pair<int, int>> rev;
rmq_t<pair<int, int>> rmq;
void dfs(int v, int p){
max_prof[v] = prof[v];
in[v] = (int) rev.size();
rev.emplace_back(in[v], v);
for(auto [w, u] : g[v]) if(u != p){
par[u] = v;
prof[u] = prof[v] + w;
max_prof[v] = max(max_prof[v], prof[u]);
dfs(u, v);
rev.emplace_back(in[v], v);
}
out[v] = (int) rev.size();
rev.emplace_back(in[v], v);
}
lca_t(){}
lca_t(const auto & adj, int root = 0) : N(int(adj.size())), in(N), out(N), par(N), prof(N), max_prof(N), g(adj){
rev.reserve(3*N);
par[root] = root;
dfs(root, root);
rmq = rmq_t(rev);
}
int lca(int u, int v){
u = in[u], v = in[v];
if(u > v) swap(u, v);
return rmq.query(u, v+1).second;
}
int64_t dist(int u, int v){
int l = lca(u, v);
return prof[u] + prof[v] - 2 * prof[l];
}
bool is_ancestor(int a, int b){
return in[a] < in[b] && out[a] > out[b];
}
};
int main(){
cin.tie(0)->sync_with_stdio(false);
int n, q;
cin>>n>>q;
int64_t all_edges = 0;
vector<vector<pair<int64_t, int>>> g(n);
for(int e =0; e < n-1; e++){
int u, v; int64_t w;
cin>>u>>v>>w;
all_edges += w;
u--, v--;
g[u].emplace_back(w,v);
g[v].emplace_back(w,u);
}
vector<lca_t> lcas(n);
for(int r = 0; r < n; r++){
lcas[r] = lca_t(g, r);
}
while(q--){
int start, key, trap;
cin>>start>>key>>trap;
start--, key--, trap--;
if(lcas[start].is_ancestor(trap, key)){
cout<<"impossible\n";
continue;
}
int64_t maxi = 0;
int l = lcas[start].lca(key, trap);
int cur = key, last = -1;
while(true){
for(auto [w,v] : g[cur]) if(v != lcas[start].par[cur]){
if(v == last) continue;
//cout<<cur+1<<" --> "<<v+1<<" = "<<lcas[start].max_prof[v] - (lcas[start].prof[cur] - lcas[start].prof[l])<<"\n";
maxi = max(maxi, lcas[start].max_prof[v] - (lcas[start].prof[cur] - lcas[start].prof[l]));
}
if(cur == l) break;
last = cur;
cur = lcas[start].par[cur];
}
while(true){
for(auto [w,v] : g[cur]) if(v != lcas[start].par[cur]){
if(v == last) continue;
//cout<<cur+1<<" --> "<<v+1<<" = "<<lcas[start].max_prof[v]<<"\n";
maxi = max(maxi, lcas[start].max_prof[v]);
}
if(cur == start) break;
last = cur;
cur = lcas[start].par[cur];
}
int64_t answer = 2*all_edges - maxi;
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: 3708kb
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:
318 310 310 impossible 314
result:
wrong answer 1st lines differ - expected: '316', found: '318'