QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197928 | #5372. 杀蚂蚁简单版 | zhaohaikun | 25 | 48ms | 23420kb | C++14 | 2.4kb | 2023-10-02 22:01:39 | 2023-10-02 22:01:39 |
Judging History
answer
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> inline void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 1e5 + 10, MOD = 998244353;
int n, q, val[N], vv[N], sum1[N], sum2[N], sum3[N], tot[N], fa[N];
int st[21][N], lg[N], dfn[N], rdfn[N], dfscnt;
vector <int> v[N];
inline int power(int x, int y = MOD - 2) {
int ans = 1;
for (; y; x = (ll) x * x % MOD, y >>= 1)
if (y & 1) ans = (ll) ans * x % MOD;
return ans;
}
void dfs(int x, int fa) {
st[0][dfn[x] = ++dfscnt] = ::fa[x] = fa;
vv[x] = power((ll) val[1] * val[2] % MOD);
for (int i: v[x]) tot[x] = (tot[x] + val[i]) % MOD;
sum1[x] = (sum1[fa] + vv[x]) % MOD;
sum2[x] = (sum2[fa] + (ll) tot[x] * val[x]) % MOD;
sum3[x] = (sum3[fa] + (ll) tot[x] * val[x] % MOD * sum1[x]) % MOD;
for (int i: v[x])
if (i != fa) dfs(i, x);
rdfn[x] = dfscnt;
}
int marx(int x, int y) {
return dfn[x] < dfn[y] ? x : y;
}
int lca(int x, int y) {
if (x == y) return x;
x = dfn[x], y = dfn[y];
if (x > y) swap(x, y);
int k = lg[y - x++];
return marx(st[k][x], st[k][y - (1 << k) + 1]);
}
signed main() {
read(n);
F(i, 1, n) read(val[i]);
F(i, 1, n - 1) {
int x, y; read(x), read(y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(2, 1);
F(i, 1, lg[n])
F(j, 1, n - (1 << i) + 1)
st[i][j] = marx(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
read(q);
while (q--) {
int s, x, y; read(s), read(x), read(y);
int k = lca(x, y);
if (dfn[k] <= dfn[s] && rdfn[s] <= rdfn[k]) {
if (lca(x, s) != k) swap(x, y);
int kk = lca(y, s);
cout << ((ll) sum1[k] * (sum2[x] - sum2[fa[k]] + MOD) + (sum3[kk] - sum3[k] + MOD) + (ll) sum1[kk] * (sum2[y] - sum2[kk] + MOD)) % MOD << '\n';
} else {
int kk = lca(k, s);
cout << (ll) sum1[kk] * ((ll) sum2[x] + sum2[y] - sum2[k] - sum2[fa[k]] + MOD * 2) % MOD << '\n';
}
}
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 11828kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 3 5 1 2 4 2
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 10860kb
input:
5 1 1 1 1 1 1 2 2 3 3 4 4 5 1 2 5 3
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 0ms
memory: 10456kb
input:
5 1 1 1 1 1 1 2 2 3 3 4 3 5 1 2 5 4
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 11488kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 3 5 1 2 3 2
output:
5
result:
ok single line: '5'
Test #5:
score: 0
Accepted
time: 0ms
memory: 11144kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 2 5 1 2 4 3
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 1ms
memory: 10952kb
input:
5 1 1 1 1 1 1 2 2 3 3 4 4 5 1 2 2 4
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 1ms
memory: 11892kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 3 5 1 2 3 5
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 10044kb
input:
5 1 1 1 1 1 1 2 2 3 3 4 4 5 1 2 4 4
output:
2
result:
ok single line: '2'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #9:
score: 0
Wrong Answer
time: 12ms
memory: 11644kb
input:
100 19082214 4807200 18093892 10128508 6278227 3082640 18435935 14945221 17570657 10054626 13020781 18926050 4884255 5459284 10075080 18518993 16590687 4103633 1887923 12545378 14553360 14115988 766212 14352785 1482486 15388118 16751947 3735054 16071111 661078 10093466 972154 5931449 18167107 109818...
output:
479683778 179582504 183540399 836906770 807065977 86021271 888605614 258095045 717572601 67073885 169742897 568399543 355067333 635456786 2092706 781082522 349718455 214671113 261859742 956601959 853226665 383719647 759323832 758339000 478192913 185889886 620107133 860692893 878764850 578900045 9760...
result:
wrong answer 1st lines differ - expected: '584487649', found: '479683778'
Subtask #3:
score: 15
Accepted
Test #18:
score: 15
Accepted
time: 40ms
memory: 21316kb
input:
100000 13643 13546 7538 2233 7731 14619 19601 8438 9556 19888 17313 1060 15168 11207 11183 16074 10758 7469 13444 9658 18326 4735 7542 13836 5863 7903 7212 14714 10416 18506 13435 14502 15271 13205 14887 18074 8353 19807 1767 19148 7343 10823 14211 66 17168 8305 1210 5436 18552 3659 886 18416 19261 ...
output:
470097670 143314895 319664187 989628182 724942465 549661815 490172883 264410099 250850293 913408788 466102803 464951422 764468729 755758546 475030770 300112112 603892921 747093262 967440122 1264162 552912646 26025219 721517270 275076549 191931901 678760307 278036996 360130747 791206265 491217660 742...
result:
ok 100000 lines
Test #19:
score: 0
Accepted
time: 42ms
memory: 21244kb
input:
100000 7573 7436 9984 2252 6052 18503 31 16126 1069 5378 10483 3727 7005 4516 13139 4506 1772 19471 3381 4672 4084 11319 3036 8162 11024 7475 7008 16380 9914 19726 799 4512 19169 14960 6795 10302 17405 6573 3559 3247 19148 15631 10915 2238 8989 17898 6403 5247 6255 12305 4333 12566 12779 11182 17064...
output:
111801098 172129117 404164713 445405216 276472705 757768805 625065364 789427663 291213940 933955541 775110966 215954655 184757237 78376608 695421289 283190271 631342927 937109577 739765699 460648915 303107688 807577336 800102713 525391747 153718591 26572469 923735199 220723292 163355255 988279059 88...
result:
ok 100000 lines
Test #20:
score: 0
Accepted
time: 32ms
memory: 21384kb
input:
100000 7754 10408 9345 12014 16443 15992 6537 3214 17391 323 17360 3642 367 4348 6479 3082 2128 19907 15285 12309 14348 12358 10994 16674 14123 10304 9148 7132 16185 18573 17272 15573 11229 12458 3445 13364 172 1680 11516 1811 16273 164 16239 16929 16243 13556 9921 16493 7834 17291 4354 16462 331 19...
output:
453210654 810215132 418290721 313259954 256178186 484117196 562026183 217562713 372439551 397578463 156005329 773019262 4766455 723539751 395254864 93762835 576298116 401452751 930578282 872399614 474214091 223925921 119168484 11686316 416040827 86207959 106041952 49651975 317893197 830123004 428069...
result:
ok 100000 lines
Test #21:
score: 0
Accepted
time: 41ms
memory: 23420kb
input:
100000 5309 19643 18246 2403 19394 3374 19270 810 5731 2719 6746 7858 4522 11464 18035 17849 13737 8718 18241 9358 17726 12389 5253 43 17897 1813 6933 11457 5515 16155 9885 15408 17007 10846 11884 5320 10150 18358 13863 53 8311 2327 5524 18581 6748 19632 8849 4262 10092 14484 1396 7569 15345 19096 1...
output:
291379624 423324059 381211587 357818197 753151608 403285526 514125565 110837486 982016513 10497186 809593540 602929523 695101256 660984576 774456420 672546793 953188130 912116121 57946539 470500688 646910891 765332835 893068487 715107060 458612470 953183724 595598373 183107766 871530489 918564839 72...
result:
ok 100000 lines
Test #22:
score: 0
Accepted
time: 30ms
memory: 21384kb
input:
100000 5920 6573 12338 4526 11199 8375 17599 4314 19387 16891 15577 17300 10001 11046 3960 18285 8728 12811 17135 3804 19867 2760 17394 19370 17810 10531 9917 5071 5487 18363 161 18383 10643 5463 7681 19010 3344 18901 16714 19826 1827 10997 7635 7708 11623 8594 15014 2954 3698 10765 19246 6601 11309...
output:
160940931 115530899 4812213 601251697 510424332 655277786 381970298 136574090 590412386 492845722 278421803 972193890 694437648 34618297 977711056 807689220 708392271 856644900 354773042 201731170 270294469 727036520 929682826 196035879 39101694 733354104 571766421 241946695 793407818 43865893 94975...
result:
ok 100000 lines
Test #23:
score: 0
Accepted
time: 32ms
memory: 21248kb
input:
100000 4401 18578 7878 14495 4073 5218 2175 18978 2402 12985 14033 12001 6673 12478 16028 13255 14770 12066 10426 9047 9161 3846 14849 19302 4403 643 2996 8300 19233 11644 9808 17096 9686 11951 3742 13490 15825 11744 15515 9241 1798 15991 2065 12960 6826 4443 19009 6589 1184 5375 4701 13679 1213 171...
output:
831301395 638594411 891344305 845448448 9361345 509822968 564544671 51030579 415307658 745760550 100009523 447213604 880450252 945462137 719106873 454306018 307211349 863869656 571463659 730442948 16376181 477449019 539554549 125186837 357704245 826429724 299705079 388829125 982386945 850381867 4430...
result:
ok 100000 lines
Test #24:
score: 0
Accepted
time: 44ms
memory: 21304kb
input:
100000 3028 15690 11382 16254 2938 7336 9596 6177 9036 19162 17581 4855 15766 8769 3534 2043 15259 17746 1803 9448 16559 18709 10207 4554 14923 17394 5012 19620 2684 19019 18213 6800 15468 5276 2707 10609 11767 7390 17631 4707 17139 8934 13498 11279 16812 11340 17021 2522 5244 13028 8630 14581 8091 ...
output:
478866071 422991010 796736479 413648210 679381958 344079455 397356290 557201528 30091321 61982037 19765593 894517618 911070007 840615368 662271300 609399613 172381143 288738429 112287414 100726790 422944817 946929844 731159609 945722883 193777668 809318854 737860540 102923633 562474521 201269058 980...
result:
ok 100000 lines
Test #25:
score: 0
Accepted
time: 36ms
memory: 21244kb
input:
100000 9703 9879 19456 19707 4708 13328 13830 7015 13934 9751 4851 16507 4857 12475 4257 2881 189 13083 16697 19889 6371 8422 2204 15333 1531 3482 12008 6061 9841 7264 11656 13703 15379 13664 12292 17424 6858 6313 9035 603 5936 1136 7035 14559 447 8094 10365 6584 6163 5227 9033 17649 18607 7244 2246...
output:
767413222 150335186 117139358 144284167 725165065 764712666 450613318 874236822 827594343 583534039 487021797 379868824 491043695 323905545 594414754 106513578 983539609 375942467 362192405 913442810 638446489 352304149 71778116 406612047 503608586 275627439 713412732 612358985 107217516 119571777 3...
result:
ok 100000 lines
Test #26:
score: 0
Accepted
time: 32ms
memory: 21312kb
input:
100000 5436 16201 10289 17004 11545 10082 777 7735 4827 16429 15251 7952 12052 5596 19390 16919 281 14309 10955 11014 9282 8699 17866 2859 11269 17217 6096 13099 12620 10169 15854 13702 15983 6401 13846 19782 8023 10045 8230 5404 225 7249 19204 17538 14407 17707 16151 8692 18740 10683 16956 6735 156...
output:
800921976 763103088 616320356 32992590 908247266 290731427 255933478 940716988 8977335 194390620 959199650 469826271 770433088 145975702 746602612 358812095 410102171 544116499 48491232 17126887 81756856 716240689 352495413 429118333 407571056 618622755 655793451 464834091 943023824 97235389 4594553...
result:
ok 100000 lines
Subtask #4:
score: 0
Wrong Answer
Dependency #3:
100%
Accepted
Test #27:
score: 0
Wrong Answer
time: 48ms
memory: 21324kb
input:
100000 6366 6095 19030 6124 8086 14772 14309 19146 17241 142 18854 9323 10715 7832 750 2271 19721 2209 18189 8854 6880 3105 18767 8829 10874 14605 4407 19745 567 9069 18918 16912 7413 7158 8432 4813 6416 12018 3436 19664 19454 5390 11126 10129 6287 1766 4583 340 19233 17795 12586 12602 15639 10948 1...
output:
667463109 24033390 898775928 760829139 424903938 676510384 679733271 807818653 521278403 827385259 305519378 936323393 522380222 278799176 175453239 269137604 60479594 72898464 752715660 501960373 889324171 730733085 813647558 77860556 253563817 214004911 133682405 452543506 944726712 327303110 7963...
result:
wrong answer 1st lines differ - expected: '491542341', found: '667463109'
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%