QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90920#5102. Dungeon Crawler_skb_WA 2ms3996kbC++173.5kb2023-03-26 03:39:502023-03-26 03:39:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-26 03:39:53]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3996kb
  • [2023-03-26 03:39:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;

struct debug {
#define contPrint { *this << "["; \
        int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
        *this << "]"; return *this;}
 
    ~debug(){cerr << endl;}
    template<class c> debug& operator<<(c x) {cerr << x; return *this;}
    template<class c, class d>
    debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")"; 
        return *this;}
    template<class c> debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};

#define dbg(x) "[" << #x << ": " << x << "]  "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() << 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);

const int N = 2002;
vector<pair<int, int>> G[N];
int max_path[N][N];
i64 max_path_cost[N][N][2];
int edge_cost[N][N];
int P[N][N];

i64 dfs(int cur, int root, int p)
{
    i64 mx = 0;
    i64 mx2 = 0;
    i64 which = -1;
    P[root][cur] = p;

    for(auto it : G[cur]) {
        if(it.first != p) {
            i64 x = dfs(it.first, root, cur) + it.second;
            if(x > mx) {
                mx2 = mx;
                mx = x;
                which = it.first;
            } else if(x == mx) {
                mx2 = mx;
            }
        }
    }
    max_path[root][cur] = which;
    max_path_cost[root][cur][0] = mx;
    max_path_cost[root][cur][1] = mx2;
    return mx;
}

int main() 
{
    int n, q;
    scanf("%d %d", &n, &q);

    i64 tot_cost = 0;

    for(int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
        edge_cost[u][v] = w;
        edge_cost[v][u] = w;
        tot_cost += w + w;
    }

    for(int i = 1; i <= n; i++) dfs(i, i, 0);

    int stk[N];
    int idx = 0;

    int vis[N];
    memset(vis, 0, sizeof vis);

    // Wa() dbg(tot_cost);

    while(q--) {
        int root, key, trap;
        scanf("%d %d %d", &root, &key, &trap);

        int cur = key;
        while(cur != root) {
            stk[idx++] = cur;
            vis[cur] = 1;
            cur = P[root][cur];
        }
        stk[idx++] = cur;
        vis[cur] = 1;

        if(vis[trap]) {
            puts("impossible");
        } else {
            int lca = trap;
            while(!vis[lca]) {
                lca = P[root][lca];
            }

            cur = root;
            int last = root;

            while(max_path[root][cur] != -1) {
                if(vis[cur]) last = cur;
                cur = max_path[root][cur];
            }
            if(vis[cur]) last = cur;

            if(lca == key) {
                printf("%lld\n", tot_cost - max_path_cost[root][root][0]);
            } else {
                i64 ans = 1e18;
                i64 cur_sum = 0;
                cur = root;
                while(cur != last) {
                    ans = min(ans, tot_cost + cur_sum - max_path_cost[root][cur][1]);
                    // Wa() dbg(ans);
                    cur_sum += edge_cost[cur][max_path[root][cur]];
                    cur = max_path[root][cur];
                }
                ans = min(ans, tot_cost + cur_sum - max_path_cost[root][cur][0]);
                // Wa() dbg(ans);
                printf("%lld\n", ans);
            }
        }

        while(idx > 0) {
            vis[stk[--idx]] = 0;
        }
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3996kb

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
328

result:

wrong answer 5th lines differ - expected: '314', found: '328'