QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386928 | #5102. Dungeon Crawler | Energy_is_not_over# | WA | 1ms | 3800kb | C++17 | 3.9kb | 2024-04-11 21:38:30 | 2024-04-11 21:38:31 |
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<pair<int, int>> leaves;
int p[max_n];
bool good[max_n];
int lst_good = -1;
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;
p[cur] = pr;
// 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 dfs2(int cur, int pr) {
int pr_good = lst_good;
if (good[cur]) {
lst_good = cur;
}
if (v[cur].size() == 1) {
leaves.emplace_back(cur, lst_good);
}
for (auto to : v[cur]) {
if (to.F != pr) {
dfs2(to.F, cur);
}
}
lst_good = pr_good;
}
void solve(int root) {
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;
}
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;
}
}
memset(good, 0, sizeof(good));
good[k] = 1;
int pk = k;
while(p[pk] != -1 && p[pk] != lca && is_pr(lca, p[pk])) {
pk = p[pk];
good[pk] = 1;
}
lst_good = -1;
leaves.clear();
dfs2(0, -1);
ll ans_best = 1e18;
for (pair<int, int> x : leaves) {
int l = x.F, g = x.S;
ll ans_cur;
if (g == -1) {
ans_cur = SUM - d[l];
} else {
ans_cur = SUM - d[l] + 2 * (d[g] - d[lca]);
}
ans_best = min(ans_best, ans_cur);
}
ans[ind] = ans_best;
}
}
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: 100
Accepted
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:
316 293 293 impossible 314
result:
ok 5 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3800kb
input:
100 100 1 2 289384 2 3 930887 2 4 692778 4 5 636916 4 6 747794 4 7 238336 4 8 885387 8 9 760493 8 10 516650 8 11 641422 8 12 202363 8 13 490028 8 14 368691 8 15 520060 8 16 897764 16 17 513927 16 18 180541 16 19 383427 16 20 89173 16 21 455737 16 22 5212 16 23 595369 16 24 702568 16 25 956430 16 26 ...
output:
103526917 103484292 104479933 104379596 104405611 104775512 104406822 105291604 103838430 103575842 103723810 104175650 105894571 104509242 103971939 105376499 105223283 104153426 105082245 104385328 104130613 104800548 107403226 104138329 103769253 103474724 104044745 104385328 103575842 105460460 ...
result:
wrong answer 3rd lines differ - expected: '106288816', found: '104479933'