QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#368964 | #5102. Dungeon Crawler | installb | TL | 223ms | 174700kb | C++23 | 2.5kb | 2024-03-27 18:34:51 | 2024-03-27 18:34:53 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("mmx,avx2,sse2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
vector <pair <int,int> > G[N];
int n,Q;
int dfc = 0,dfn[N][N],siz[N][N],dep2[N][N];
ll dep[N][N];
short mi[N][13][N],LOG[N];
void init_dfs(int u,int f,int rt){
dfn[rt][u] = ++ dfc;
mi[rt][0][dfn[rt][u]] = f;
siz[rt][u] = 1;
dep2[rt][u] = dep2[rt][f] + 1;
for(auto [v,w] : G[u]){
if(v == f) continue;
dep[rt][v] = dep[rt][u] + w;
init_dfs(v,u,rt);
siz[rt][u] += siz[rt][v];
}
}
ll sumw2 = 0;
int get_lca(int u,int v,int s){
if(u == v) return u;
if(dfn[s][u] > dfn[s][v]) swap(u,v);
u = dfn[s][u]; v = dfn[s][v];
int d = LOG[v - u++];
return dep2[s][mi[s][d][u]] < dep2[s][mi[s][d][v - (1 << d) + 1]] ? mi[s][d][u] : mi[s][d][v - (1 << d) + 1];
}
void solve(){
cin >> n >> Q;
for(int u,v,w,i = 1;i < n;i ++){
cin >> u >> v >> w;
// u = 1; v = i + 1; w = 1000000000;
G[u].push_back({v,w});
G[v].push_back({u,w});
sumw2 += 2ll * w;
}
LOG[0] = -1; for(int i = 1;i <= n;i ++) LOG[i] = LOG[i >> 1] + 1;
for(int s = 1;s <= n;s ++){
dep[s][s] = dep2[s][s] = 0; dfc = 0;
init_dfs(s,0,s);
for(int i = 1;i <= LOG[n];i ++){
for(int j = 1;j + (1 << (i - 1)) <= n;j ++){
mi[s][i][j] = dep2[s][mi[s][i - 1][j]] < dep2[s][mi[s][i - 1][j + (1 << (i - 1))]] ? mi[s][i - 1][j] : mi[s][i - 1][j + (1 << (i - 1))];
}
}
}
vector <int> lef;
for(int i = 1;i <= n;i ++){
if(G[i].size() == 1) lef.push_back(i);
}
for(int s,k,t,i = 1;i <= Q;i ++){
cin >> s >> k >> t;
// s = 1; k = 2; t = 3;
ll ans = LLINF;
for(int u : lef){
if(u != s){
ll dk = dep[s][get_lca(u,k,s)];
ll dt = dep[s][get_lca(u,t,s)];
ans = min(ans,sumw2 - dep[s][u] + 2 * max(0ll,dk - dt));
// cout << u << ' ' << get_lca(u,k,s) << ' ' << dk << ' ' << dt << ' ' << ans << endl;
}
}
if(dfn[s][t] <= dfn[s][k] && dfn[s][k] <= dfn[s][t] + siz[s][t] - 1) cout << "impossible\n";
else cout << ans << '\n';
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8552kb
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: 0
Accepted
time: 2ms
memory: 9908kb
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 106288816 104379596 104405611 104775512 105434682 105291604 103838430 105371370 104677980 104175650 105894571 104509242 103971939 105376499 105223283 104153426 105082245 105413188 104130613 104800548 106846555 104138329 103769253 105456754 104044745 104385328 106973740 105460460 ...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 6116kb
input:
10 6 1 2 4 2 3 7 2 4 8 4 5 6 4 6 4 4 7 6 4 8 7 8 9 3 8 10 10 3 8 1 10 4 7 1 7 3 7 2 9 8 10 3 4 1 6
output:
99 78 97 87 88 93
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 5916kb
input:
10 9 9 2 5 9 1 6 9 4 97 9 7 2 9 8 42 9 10 11 9 6 77 9 3 14 9 5 9 4 7 10 7 3 8 8 7 9 1 4 8 10 7 4 7 1 2 10 1 5 10 7 2 8 4 10
output:
352 427 impossible 443 418 427 418 418 407
result:
ok 9 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 6132kb
input:
9 9 2 3 48 9 5 31 7 3 97 4 3 16 1 7 24 5 3 82 8 2 51 6 4 33 1 2 8 3 6 8 1 6 3 9 5 6 2 6 4 5 6 1 9 6 4 2 8 9 4 9 2
output:
530 643 impossible 530 impossible 561 impossible 595 627
result:
ok 9 lines
Test #6:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
8 9 1 7 51 7 6 86 2 3 62 8 4 72 5 6 17 4 1 75 3 1 41 2 3 7 5 8 4 6 1 3 8 6 2 4 2 7 8 5 6 2 1 5 7 1 6 6 7 8
output:
551 impossible 524 558 579 impossible 551 705 524
result:
ok 9 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 6124kb
input:
9 9 5 4 13 9 2 10 1 9 25 7 6 34 4 2 77 3 8 67 8 1 57 6 9 100 6 4 1 4 1 7 3 2 9 4 9 7 7 9 3 6 2 1 2 8 4 8 6 2 6 5 9
output:
517 545 impossible 530 483 517 642 584 impossible
result:
ok 9 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
10 10 2 4 26 9 8 39 4 5 88 6 3 70 7 6 7 10 4 41 8 3 57 1 6 15 5 6 9 2 8 6 3 9 1 5 7 8 4 7 8 7 6 4 2 7 3 6 8 2 5 4 10 4 8 9 1 5 9
output:
impossible 496 529 441 531 415 566 529 441 523
result:
ok 10 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 5908kb
input:
10 9 3 2 6 2 1 18 8 1 44 1 9 42 6 3 72 10 8 46 7 10 93 5 3 11 4 10 13 7 3 1 8 2 5 7 5 4 5 10 8 3 1 4 6 4 3 10 1 6 5 10 8 2 10 4
output:
impossible 550 584 impossible 483 impossible 504 impossible 489
result:
ok 9 lines
Test #10:
score: 0
Accepted
time: 223ms
memory: 174700kb
input:
2000 199998 126 244 481188299 718 1159 740107180 1327 1250 248943862 977 1092 780169400 826 27 932696654 1668 638 478193038 229 174 176675890 1251 646 843918836 102 1973 593920932 236 218 165399894 760 151 890198591 232 502 10739184 1961 1409 45917915 548 1840 974742709 1096 630 280975617 1110 1048 ...
output:
1266421864327 impossible 1003453161105 1017793822920 1056758437569 impossible 1249128162612 1233756636475 1354563020262 1275484665657 impossible impossible 1644448395794 impossible impossible impossible 1305598243001 1730425595360 1090858373772 1180211385304 1235543994987 1894692656465 impossible 12...
result:
ok 199998 lines
Test #11:
score: -100
Time Limit Exceeded
input:
1999 199999 1233 1172 270406027 1233 238 118916774 1233 902 452751000 1233 1868 96683385 1233 605 546735354 1233 82 679125014 1233 1132 938320209 1233 1424 561568050 1233 113 835230774 1233 330 63962348 1233 1758 986726048 1233 1006 214588798 1233 88 433116365 1233 1122 412164831 1233 1496 846865689...
output:
1993724469968 1993337272038 1993488034133 1993680602118 1993694627446 1994104485073 1994062829494 1993917179450 1993435921379 1993814292350 1993428850371 1993220985867 1993782751870 1994075401526 1993846887971 1994090631242 1993936573248 1993321397280 1993351664812 1993207502090 1994025398060 199385...