QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197928#5372. 杀蚂蚁简单版zhaohaikun25 48ms23420kbC++142.4kb2023-10-02 22:01:392023-10-02 22:01:39

Judging History

你现在查看的是最新测评结果

  • [2023-10-02 22:01:39]
  • 评测
  • 测评结果:25
  • 用时:48ms
  • 内存:23420kb
  • [2023-10-02 22:01:39]
  • 提交

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%