QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386830#5102. Dungeon CrawlerEnergy_is_not_over#WA 0ms3780kbC++173.1kb2024-04-11 20:30:352024-04-11 20:30:35

Judging History

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

  • [2024-04-11 20:30:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3780kb
  • [2024-04-11 20:30:35]
  • 提交

answer

//
// Stvoreno ENERGom o 11.04.24. 13:44:56
//

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define F first
#define fir first
#define S second
#define sec second
#define mp make_pair
#define MP make_pair
#define pb push_back
#define PB push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy
#define DEBUG for (int _____DEBUG=1;_____DEBUG;_____DEBUG=0)

template<class ...Ts>
auto &PRNT(Ts ...ts) { return ((cerr << ts << " "), ...); }

#define LOG(...) PRNT(#__VA_ARGS__" ::",__VA_ARGS__)<<endl
#else
#define DEBUG while (0)
#define LOG(...)
#endif

const int max_n = 2011, max_q = 200111, inf = 1000111222;

vector<pair<int, int>> v[max_n];
int n, cnt_q;
// qind, key, trap
vector<pair<int, pair<int, int>>> q[max_n];
ll ans[max_q];
ll d[max_n];
int tin[max_n];
int tout[max_n];
int cur_t = 0;
vector<int> leaves;

bool is_pr(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}
ll SUM = 0;

void dfs(int cur, int pr, ll cur_d) {
    tin[cur] = cur_t++;
    d[cur] = cur_d;
    if (v[cur].size() == 1) {
        leaves.push_back(cur);
    }
    for (auto p : v[cur]) {
        int to = p.F, w = p.S;
        if (to == pr) continue;
        dfs(to, cur, cur_d + w);
    }
    tout[cur] = cur_t++;
}

void solve(int root) {
    leaves.clear();
    cur_t = 0;
    dfs(root, -1, 0);
    ll mx_d = 0;
    for (int i = 0; i < n; ++i) {
        mx_d = max(mx_d, d[i]);
    }
    for (auto qq : q[root]) {
        int ind = qq.F;
        int k = qq.S.F, t = qq.S.S;
        if (is_pr(t, k)) {
            ans[ind] = -1;
            continue;
        }
        if (is_pr(k, t)) {
            ans[ind] = SUM - mx_d;
            continue;
        }
        ll ans1 = 1e18;
        for (int l : leaves) {
            if (is_pr(k, l)) continue;
            ans1 = min(ans1, SUM - d[l]);
        }
        ll ans2 = SUM - mx_d;
        int lca = -1;
        for (int i = 0; i < n; ++i) {
            if (!is_pr(i, k) || !is_pr(i, t)) continue;
            if (lca == -1 || d[i] > d[lca]) {
                lca = i;
            }
        }
        ans2 += 2 * (d[k] - d[lca]);
        ans[ind] = min(ans1, ans2);
    }
}

int main() {
//    freopen("input_b.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> cnt_q;
    for (int i = 0; i + 1< n; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        v[a].emplace_back(b, w);
        v[b].emplace_back(a, w);
        SUM += w;
        SUM += w;
    }
    for (int i = 0; i < cnt_q; ++i) {
        int s, k, t;
        cin >> s >> k >> t;
        --s, --k, --t;
        q[s].emplace_back(i, MP(k, t));
    }
    for (int i = 0; i < n; ++i) {
        solve(i);
    }
    for (int i = 0; i < cnt_q; ++i) {
        if (ans[i] == -1) {
            cout << "impossible\n";
        } else {
            cout << ans[i] << "\n";
        }
    }
    exit(0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3780kb

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:

293
293
293
impossible
294

result:

wrong answer 1st lines differ - expected: '316', found: '293'