QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382248#5102. Dungeon CrawlerUFRJWA 1ms3708kbC++203.8kb2024-04-08 08:14:372024-04-08 08:14:37

Judging History

你现在查看的是最新测评结果

  • [2024-04-08 08:14:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3708kb
  • [2024-04-08 08:14:37]
  • 提交

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'