QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#66146 | #5102. Dungeon Crawler | b4xji4 | AC ✓ | 2395ms | 113596kb | C++ | 3.3kb | 2022-12-07 01:14:46 | 2022-12-07 01:14:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
// Path: start -> key -> trap -> finish
// LCA + DP
// O(rooms * scenarios)
inline int read()
{
re int t = 0;
re char v = getchar();
while(v < '0') v = getchar();
while(v >= '0') t = (t<<3) + (t<<1) + v - 48, v = getchar();
return t;
}
const int M = 998244353;
inline void add(re int &x, re int &y) {(x+=y) >= M ? x-=M : x;}
inline int Mod(re int x) {return x>=M ? x-M : x;}
inline int ksm(re int x, re int y)
{
re int s = 1;
while(y)
{
if(y&1) s = 1ll * s * x % M;
x = 1ll * x * x % M, y >>= 1;
}
return s;
}
vector<int> E[2002], W[2002]; // record corridors and time
int rt, tim;
int siz[2002][2002]; // length (i,j)
int dfn[2002][2002]; // depth of node j when root = i
int fa[2002][2002];
ll dis[2002][2002]; // time (i,j)
ll Mx[2002][2002];
inline void dfs(re int x, re int y) // dfs with dp
{
siz[rt][x] = 1, dfn[rt][x] = ++tim, fa[rt][x] = y, Mx[rt][x] = dis[rt][x];
for(re int i = 0; i < E[x].size(); ++i)
{
if(E[x][i]^y)
{
dis[rt][E[x][i]] = dis[rt][x] + W[x][i];
dfs(E[x][i],x);
siz[rt][x] += siz[rt][E[x][i]];
Mx[rt][x] = max(Mx[rt][x], Mx[rt][E[x][i]]);
}
}
}
inline bool in(re int x, re int y, re int z)
{
return dfn[x][z] >= dfn[x][y] && dfn[x][z] < dfn[x][y]+siz[x][y];
}
inline int lca(re int x, re int y, re int z) // lowest common ancestor
{
while(y^z)
{
if(dfn[x][y] > dfn[x][z])
y = fa[x][y];
else
z = fa[x][z];
}
return y;
}
int main()
{
int rooms = read(), scenarios = read();
ll sum = 0;
for(re int i = 1; i < rooms; ++i)
{
re int u = read(), v = read(), time = read();
E[u].push_back(v), E[v].push_back(u);
W[u].push_back(time), W[v].push_back(time);
sum += time;
}
for(re int i = 1; i <= rooms; ++i)
{
rt = i;
tim = 0;
dfs(i,i); // dfs from root = i; dp for each scenario
}
while(scenarios--)
{
re int start = read(), key = read(), trap = read();
re ll mx = 0;
if(in(start,key,trap)) // key first trap second
{
for(re int i = 1; i <= rooms; ++i)
mx = max(mx, dis[start][i]);
printf("%lld\n", sum+sum-mx);
}
else if(in(start,trap,key)) // trap first key second
puts("impossible");
else
{
re int o = lca(start,trap,key), oy = key;
while(fa[start][key]^o) key = fa[start][key];
for(re int i = 1; i <= rooms; ++i)
{
if(!in(start,key,i))
mx = max(mx, dis[start][i]);
}
ll tmp = sum+sum-mx;
int lst = 0;
while(oy^o)
{
tmp = min(tmp, sum+sum-dis[start][oy]+dis[o][oy]*2);
for(auto z : E[oy])
{
if(z^fa[start][oy] && z^lst)
tmp = min(tmp, sum+sum-Mx[start][z]+dis[o][oy]*2);
}
lst = oy, oy = fa[start][oy];
}
printf("%lld\n", tmp);
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7984kb
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: 5ms
memory: 7508kb
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: 2ms
memory: 7832kb
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: 5768kb
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: 4ms
memory: 7964kb
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: 4ms
memory: 7808kb
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: 7820kb
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: 2ms
memory: 10012kb
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: 7832kb
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: 1837ms
memory: 113504kb
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: 0
Accepted
time: 1460ms
memory: 113284kb
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...
result:
ok 199999 lines
Test #12:
score: 0
Accepted
time: 2351ms
memory: 113396kb
input:
1998 200000 1348 321 767897262 732 563 244247276 1747 898 143621738 952 79 216678072 693 645 383457558 1061 1084 597211706 1068 1108 69631436 1493 1279 46833316 370 83 741751233 668 234 400581789 1254 807 277405261 246 71 317177072 1778 1307 117275225 1679 1090 454166908 423 1563 270094514 130 1297 ...
output:
1975372410410 1975372410410 1975935828356 1973304488995 1973667551620 1975779404141 1976066886120 1976572750087 1975072593898 1977014789030 1976101190261 1974138271828 1976530258945 1973684336396 1974554366471 1975605779407 1976303286574 1973805733832 1976072007649 1976514431746 1975901590393 197654...
result:
ok 200000 lines
Test #13:
score: 0
Accepted
time: 2395ms
memory: 113244kb
input:
1998 199998 594 1154 556527904 735 443 423596386 1775 1615 848547206 1671 1234 171000231 1249 1663 374475402 1917 1121 196759581 57 938 746868584 419 1221 887950273 27 317 850167013 1705 1846 322466225 1836 1777 477834411 1849 368 867004000 1256 1610 326093012 1818 1283 820339723 318 1062 759021533 ...
output:
1995392439974 1995757588621 1993551901352 1997160271122 1994401952822 1995034800943 1995113419987 1996096973937 1996396691787 1995491012221 1994645387960 1992363649700 1996323764542 1994438892340 1993053180618 1994462180483 1996598423828 1993492716164 1993933259456 1995045031681 1995823020651 199724...
result:
ok 199998 lines
Test #14:
score: 0
Accepted
time: 1875ms
memory: 113284kb
input:
2000 200000 890 129 1 1213 391 5558532 456 1286 485419380 1284 836 44 660 1033 1 1967 1692 57 1855 607 1 376 1842 1365940 33 659 612 1639 57 40587 1003 201 44446 184 1292 3657 1406 1836 13902332 239 811 519 1331 319 749826 218 1953 6 1981 1964 3 399 1468 27074 600 769 99493262 1527 772 135364 1413 1...
output:
130105184557 130664308004 impossible impossible 130572294036 136262248567 132268782882 131522790821 impossible impossible 195732356541 136571824140 impossible 133902865084 198087210081 133285529827 132105222970 133329460037 impossible 133329465092 impossible 130974095425 130664461705 130572294035 13...
result:
ok 200000 lines
Test #15:
score: 0
Accepted
time: 60ms
memory: 113400kb
input:
2000 1 1 2 1000000000 1 3 1000000000 1 4 1000000000 1 5 1000000000 1 6 1000000000 1 7 1000000000 1 8 1000000000 1 9 1000000000 1 10 1000000000 1 11 1000000000 1 12 1000000000 1 13 1000000000 1 14 1000000000 1 15 1000000000 1 16 1000000000 1 17 1000000000 1 18 1000000000 1 19 1000000000 1 20 10000000...
output:
3997000000000
result:
ok single line: '3997000000000'
Test #16:
score: 0
Accepted
time: 148ms
memory: 113380kb
input:
2000 10000 180 898 89933 180 402 94 1651 1978 81813 180 1751 888228132 1077 180 27685083 180 1060 1 180 1364 8058 891 180 551 571 180 9622824 1448 180 10 1625 180 100 180 589 1 394 1712 1 180 256 6783346 414 1323 9 730 180 515 1472 180 1 453 180 3773589 1879 180 1 180 1378 96 180 1537 810641 180 125...
output:
203980410655 204049851467 204049908386 204049899759 204046341687 204049898312 204047592926 203540720521 204049908495 204049899089 204049908508 204049902864 204049905993 204049900884 204049908407 204049908506 204049035506 204049903756 204049908508 204049908508 204049908508 204043615125 204047951190 2...
result:
ok 10000 lines
Test #17:
score: 0
Accepted
time: 177ms
memory: 112364kb
input:
1978 10000 1889 707 3446042 940 201 787264 320 530 1 384 1335 9 1240 573 29465949 1386 1057 326096 1480 1315 93058261 1102 1859 714 1880 427 1 1102 695 1 598 926 1 1798 1394 8 1163 1000 272812 1315 158 18777779 335 387 8203 1302 1240 54 1569 335 253898040 1346 1824 21947201 1102 1720 6 1057 1248 749...
output:
182382194473 182760498808 181884622285 182767131929 182750533270 183362723595 182731182731 183310694189 182755949668 182722084400 182382235729 182755858463 182106594742 182726172939 182087778648 182766416644 182758294562 182720967383 182473853665 182755948088 183310756861 182451480636 182451486002 1...
result:
ok 10000 lines
Test #18:
score: 0
Accepted
time: 4ms
memory: 7788kb
input:
6 9 1 2 1 2 3 1 1 4 2000 2 5 5000 3 6 8000 4 1 3 5 1 3 6 1 3 4 3 1 5 3 1 6 3 1 2 4 6 1 5 6 1 6 5
output:
20002 17003 impossible impossible 17005 17003 22003 22002 25003
result:
ok 9 lines
Test #19:
score: 0
Accepted
time: 204ms
memory: 113504kb
input:
2000 10000 1374 1406 171121 529 147 76 1419 179 2 1913 314 5928 772 1768 871 1809 1434 14978 304 867 33909 613 1267 643 579 1575 441086863 954 1628 199 637 514 24 1105 1201 410 946 828 850 1028 629 95496 794 1668 5139 1471 1146 27 500 654 1863190 1006 794 29256 25 887 272340 966 471 96 303 1890 8899...
output:
impossible 129013534188 impossible 139592478932 168707270454 impossible impossible 213643633814 impossible 152956304222 177219440395 impossible 176555757699 183717875187 159103517800 170550798505 impossible impossible 144257517764 141735131233 123067707906 152762288328 151029434818 impossible 138947...
result:
ok 10000 lines
Test #20:
score: 0
Accepted
time: 204ms
memory: 113204kb
input:
1996 10000 59 233 25077562 1226 998 68480 442 1909 964 302 1728 68702601 1022 276 75822 739 1190 2065150 1803 1146 2517 561 1473 45 52 379 1 277 470 88019 867 859 11763126 167 1033 975175468 1291 463 61 1210 303 858 1879 652 61651 436 238 112462557 1799 81 13718 295 1255 5790325 1642 1806 350871208 ...
output:
212629172974 212425245241 212627530398 212191899504 212093645571 212633083827 212733787356 212852651413 212644232711 211690644080 212733725683 212302994429 212711891397 212059999422 212732606585 210988964926 212362700241 212546678735 212729098689 212651334235 212586153248 210763052308 212317295461 2...
result:
ok 10000 lines
Test #21:
score: 0
Accepted
time: 245ms
memory: 113152kb
input:
1998 10000 863 1521 2278 862 476 57 975 1396 2558359 502 8 851298 1308 178 8510 1736 720 58348 390 1115 357 1775 366 2602 1718 1747 5 1884 553 2764 1864 921 1 1672 654 3 1265 948 13795446 528 1618 939 1851 1568 18724092 1238 1912 2289 819 1772 618 1318 455 80 160 1046 428386 1008 1615 79779915 884 1...
output:
188524321860 188459301950 188523253691 188523500670 188280316699 188506435186 188510684450 188220540690 188517900899 188519088924 188505926020 187792474828 188517825924 188514315427 188511627014 188406079966 188378351609 187534795044 188741512335 188419202729 187706668157 188489471102 188519205214 1...
result:
ok 10000 lines
Test #22:
score: 0
Accepted
time: 87ms
memory: 113596kb
input:
2000 2 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 10 11 1000000000 11 12 1000000000 12 13 1000000000 13 14 1000000000 14 15 1000000000 15 16 1000000000 16 17 1000000000 17 18 1000000000 18 19 1000000000 19 2...
output:
1999000000000 impossible
result:
ok 2 lines
Extra Test:
score: 0
Extra Test Passed