QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386830 | #5102. Dungeon Crawler | Energy_is_not_over# | WA | 0ms | 3780kb | C++17 | 3.1kb | 2024-04-11 20:30:35 | 2024-04-11 20:30:35 |
Judging History
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'