QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380213#5102. Dungeon CrawlerUFRJ#WA 1ms3580kbC++202.3kb2024-04-06 21:50:312024-04-06 21:50:32

Judging History

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

  • [2024-04-06 21:50:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3580kb
  • [2024-04-06 21:50:31]
  • 提交

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'