QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#64976 | #5102. Dungeon Crawler | visho33 | WA | 3ms | 4920kb | C++14 | 2.9kb | 2022-11-26 08:37:56 | 2022-11-26 08:37:58 |
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[s].query(k, u);
int lca2 = tree[s].query(t, u);
diff = max(diff, tree[s].d[u] - 2LL*max(0, tree[s].d[lca1] - tree[s].d[lca2]));
}
cout << sum - diff << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3588kb
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: 3ms
memory: 4920kb
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 104360163 103838430 104379596 104405611 104775512 106268596 105291604 103838430 104849674 105585584 104175650 105894571 104509242 105945437 105376499 105223283 104153426 105082245 106247102 104130613 104800548 103924980 104138329 103769253 103474724 104044745 104385328 103575842 105460460 ...
result:
wrong answer 2nd lines differ - expected: '103484292', found: '104360163'