QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#64975 | #5102. Dungeon Crawler | visho33 | WA | 1ms | 3536kb | C++14 | 2.9kb | 2022-11-26 08:34:32 | 2022-11-26 08:34:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
vector<vector<ii>> edges;
vector<int> log1;
struct Tree{
int n;
int root;
vector<int> first1;
vector<int> vis;
vector<int> euiler;
vector<int> old_ind;
vector<int> d;
vector<vector<int> > v;
void dfsxd(int i, int par){
int new_ind = old_ind.size();
old_ind.push_back(i);
first1[i] = euiler.size();
euiler.push_back(new_ind);
for(auto x: edges[i]){
if(x.first != par){
dfsxd(x.first, i);
}
euiler.push_back(new_ind);
}
return;
}
void sparse(int n){
int p=log1[n];
vector<int> v1(n+1,0);
for(int i=0;i<=p;i++) v.push_back(v1);
for(int i=1;i<=n;i++){
v[0][i]=euiler[i];
}
for(int j=1;j<=p;j++){
int len=(1<<j);
int len1=len/2;
for(int i=1;i+len-1<=n;i++){
v[j][i]=min(v[j-1][i],v[j-1][i+len1]);
}
}
return;
}
void dfs(int v, int p){
for(auto u : edges[v]){
if(u.first != p){
d[u.first] = d[v] + u.second;
dfs(u.first, v);
}
}
return;
}
public:
Tree(int nx, int rootx){
n = nx;
root = rootx;
first1.resize(n);
vis.resize(n);
d.resize(n);
dfsxd(root, -1);
sparse(euiler.size());
dfs(root, -1);
}
int query(int a, int b){
int l = first1[a];
int r = first1[b];
if(l>r){
swap(l, r);
}
int len=r-l+1;
int p=log1[len];
return min(v[p][l],v[p][r+1-(1<<p)]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
log1.resize(1005);
for(int i = 2; i<1005; i++){
log1[i] = 1 + log1[i/2];
}
int n, q;
cin >> n >> q;
ll sum = 0;
edges.resize(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
ll w;
cin >> a >> b >> w;
a--;
b--;
edges[a].push_back(ii(b, w));
edges[b].push_back(ii(a, w));
sum = sum + 2LL * w;
}
vector<Tree> tree;
for(int i = 0; i<n; i++){
tree.push_back(Tree(n, i));
}
vector<int> hojas;
for(int i = 0; i<n; i++){
if(edges[i].size() == 1){
hojas.push_back(i);
}
}
while (q--) {
int s, k, t;
cin >> s >> k >> t;
s--;
k--;
t--;
if (tree[s].d[t] + tree[t].d[k] == tree[s].d[k]) {
cout << "impossible\n";
continue;
}
ll diff = 0;
for(auto u: hojas){
int lca1 = tree[k].query(u, t);
int lca2 = tree[u].query(t, u);
diff = max(diff, tree[s].d[u] - 2LL*tree[lca1].d[lca2]);
}
cout << sum - diff << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3536kb
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:
305 316 293 impossible 286
result:
wrong answer 1st lines differ - expected: '316', found: '305'