QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#727087#4889. 愚蠢的在线法官NineSuns3 213ms34428kbC++143.0kb2024-11-09 11:24:002024-11-09 11:24:05

Judging History

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

  • [2024-11-09 11:24:05]
  • 评测
  • 测评结果:3
  • 用时:213ms
  • 内存:34428kb
  • [2024-11-09 11:24:00]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define int long long

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e5+5, mod = 998244353; 
int n, v[N], vis[N], dfn[N], sz[N], a[N], dt, ld[N], rd[N], k; 
vector <int> e[N]; 
ll qpow (ll x, ll y = mod-2) {
	ll res = 1;
	while (y) {
		if (y&1) res = res*x%mod;
		x = x*x%mod; y >>= 1;
	}
	return res; 
}
void dfs (int p, int fa) {
	sz[p] = vis[p]; 
	for (int i : e[p]) {
		if (i == fa) continue; 
		dfs(i, p); sz[p] += sz[i]; 
	}
	sort(e[p].begin(), e[p].end(), [&](int x, int y) { return sz[x] < sz[y]; });
}
void tdfs (int p, int fa) {
	ld[p] = dt+1;
	if (vis[p]) dfn[p] = ++dt; 
	for (int i : e[p]) {	
		if (i == fa) continue; 
		tdfs(i, p); 
	} 
	rd[p] = dt; 
}
ll ans = 1; 
ll sk[5005][5005], f[N], g[N]; 
ll td[N]; 
void dfs2 (int p, int fa, int k) {
	if (vis[p]) {
//		cout << p << " " << v[p] << " " << k << endl; 	
		g[dfn[p]] = (v[p]+k)%mod;
		ans = ans*(v[p]+k)%mod; 
//		cout << "SK:\n"; 
//		cout << sz[p] << endl; 
////		for (int j = dfn[p];j <= dfn[p]+sz[p]-1;j++) cout << sk[p][j] << " "; cout << endl; 
		for (int j = dfn[p]+1;j <= dfn[p]+sz[p]-1;j++) (sk[p][j] -= sk[p][dfn[p]]) %= mod; 
		for (int j : e[p]) {
			if (j == fa || !sz[j]) continue; 
//			cout << "CHJONSLKJF:" << j << " " << sz[j] << endl; 
			for (int i = ld[j];i <= rd[j];i++) sk[j][i] = 1; //sk[p][i]; 
			dfs2(j, p, -v[p]);  
//			cout << "CHECK:" << p << " " << j << " " << ld[j] << endl; 
			ll tmp = sk[p][ld[j]]; assert(tmp == 0); 
			for (int i = ld[j];i <= rd[j];i++) sk[p][i] = 0; //tmp*sk[j][i]%mod;
		}
		return; 
	}
	ll s = 0; 
	for (int i : e[p]) {
		if (i == fa || !sz[i]) continue; 
		for (int j = ld[i];j <= rd[i];j++) sk[i][j] = 1;// (sk[i][j] = sk[p][j]-s) %= mod;
		dfs2(i, p, k); 
		int tmp = (1-s)%mod; 
		for (int j = ld[i];j <= rd[i];j++) assert(sk[p][j] == sk[p][ld[i]]); 
		for (int j = ld[i];j <= rd[i];j++) sk[p][j] = tmp*sk[i][j]%mod; 
		
		for (int j = ld[i];j <= rd[i];j++) td[j] = (v[p]+k)%mod; 
		ll tk = k; 
		for (int j = ld[i];j <= rd[i];j++) {
			ll sv = qpow(g[j])*td[j]%mod; 
//			cout << p << " " << i << " " << sv << " " << td[j] << " " << g[j] << " " << j << endl; 
			(k -= (v[p]+tk)%mod*sv%mod/*sk[p][j]%mod*/) %= mod; (s += sv*sk[p][j]%mod) %= mod; 
			for (int z = j;z <= rd[i];z++) (td[z] -= sv*g[z]%mod) %= mod; 
			assert(td[j] == 0); 
		}
	}
	
}

void solve () {
	cin >> n >> k; 
	for (int i = 1;i <= n;i++) cin >> v[i]; 
	for (int i = 1;i <= k;i++) {
		cin >> a[i]; 
		if (vis[a[i]]) {
			cout << "0"; return; 
		}
		vis[a[i]] = 1; sk[1][i] = 1; 
	}
	for (int i = 1;i < n;i++) {
		int x, y; cin >> x >> y; 
		e[x].pb(y); e[y].pb(x); 
	}
	dfs(1, 0); tdfs(1, 0); 
	dfs2(1, 0, 0);  
	if (ans < 0) ans += mod; 
	cout << ans;
}

signed main () {
//	ios::sync_with_stdio(0);
//	cin.tie(0); cout.tie(0);
	int T = 1;
	while (T--) solve();
	return 0;
}

詳細信息

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 213ms
memory: 34100kb

input:

499999 500000
879485015 176694934 629415436 677018935 33186863 696674214 19586946 878479076 318116264 823399347 140314195 715329843 996129441 446979068 600062488 847953138 978347569 865596472 147980317 199880680 187953368 989585254 457868128 466175307 381871948 369138343 826894839 963935318 36550896...

output:

0

result:

ok 1 number(s): "0"

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 6
Accepted
time: 6ms
memory: 30200kb

input:

10 1
663730929 273617752 74933376 562874267 346105266 779139305 198742356 291012786 227170675 127136999
2
10 8
5 10
1 5
9 8
6 10
4 6
3 1
2 4
7 3

output:

273617752

result:

ok 1 number(s): "273617752"

Test #3:

score: 6
Accepted
time: 0ms
memory: 32224kb

input:

10 10
144077216 482507381 588297929 801675226 21569141 816295251 425507414 150613951 822735519 802838587
7 10 9 2 1 6 8 3 5 4
10 9
6 10
5 6
2 5
8 5
3 5
1 10
4 2
7 1

output:

816324383

result:

ok 1 number(s): "816324383"

Test #4:

score: 6
Accepted
time: 3ms
memory: 32288kb

input:

10 2
136932305 774891472 782708047 361400653 241613404 206577781 241535900 917672952 105332067 165467540
2 5
2 4
5 4
1 4
7 2
3 5
10 5
8 3
6 10
9 10

output:

830180673

result:

ok 1 number(s): "830180673"

Test #5:

score: 6
Accepted
time: 0ms
memory: 32312kb

input:

10 3
106669121 934163752 505411505 487296100 135689018 776930268 130240777 167200291 726820445 449323201
10 5 2
9 5
3 5
2 9
1 3
7 1
8 7
6 2
4 9
10 6

output:

516982188

result:

ok 1 number(s): "516982188"

Test #6:

score: 6
Accepted
time: 3ms
memory: 32220kb

input:

10 4
554115046 86946870 492346089 759285688 597393634 534292327 742418751 40866289 456853511 777192624
6 10 1 4
3 4
5 4
7 4
2 7
9 4
10 2
8 7
1 7
6 10

output:

525980396

result:

ok 1 number(s): "525980396"

Test #7:

score: 6
Accepted
time: 0ms
memory: 32356kb

input:

10 5
156072097 743398614 639218862 297252114 250194624 291963313 870909501 644015194 402352389 623034872
7 2 6 5 8
3 7
10 7
5 7
4 3
6 4
9 4
1 10
2 6
8 10

output:

971134438

result:

ok 1 number(s): "971134438"

Test #8:

score: 6
Accepted
time: 0ms
memory: 34364kb

input:

10 6
58754522 928459597 174632208 377936445 469281312 236879760 214372862 700076292 513613148 778426835
2 9 6 8 7 10
1 3
9 3
10 9
7 9
8 7
5 7
4 9
6 4
2 10

output:

383720205

result:

ok 1 number(s): "383720205"

Test #9:

score: 6
Accepted
time: 3ms
memory: 30196kb

input:

10 7
168762354 271736588 761917216 86643499 677986829 885713846 696532784 435399905 113862203 798130316
10 6 8 5 2 1 4
6 1
7 1
3 7
8 6
9 3
5 9
2 9
10 8
4 5

output:

336844044

result:

ok 1 number(s): "336844044"

Test #10:

score: 6
Accepted
time: 0ms
memory: 34332kb

input:

10 8
727643452 96661577 109323043 94391368 943841820 772388814 620778403 424167899 950821917 236642846
6 2 8 1 7 3 10 4
4 6
1 4
10 6
3 4
7 3
2 6
9 10
5 1
8 2

output:

180649465

result:

ok 1 number(s): "180649465"

Test #11:

score: 6
Accepted
time: 3ms
memory: 32264kb

input:

10 9
117163394 156945447 136708770 224773742 105988662 323714230 608540583 786406145 376690056 848998167
5 3 1 8 9 4 2 10 7
2 5
3 5
10 2
7 2
4 3
6 3
1 4
9 5
8 7

output:

199480877

result:

ok 1 number(s): "199480877"

Test #12:

score: 6
Accepted
time: 3ms
memory: 32436kb

input:

10 1
310390327 26621492 98419973 106234069 846950161 118046850 174859624 961989377 51668388 989751256
10
7 1
9 1
2 7
5 7
10 9
6 9
8 2
4 2
3 5

output:

989751256

result:

ok 1 number(s): "989751256"

Test #13:

score: 6
Accepted
time: 2ms
memory: 32320kb

input:

10 10
455951699 832766533 368655882 274544983 630176565 149197662 125666866 811780187 718334218 758563081
6 4 8 5 7 1 2 10 9 3
7 1
10 1
4 7
9 7
6 10
8 10
5 4
2 4
3 9

output:

859352350

result:

ok 1 number(s): "859352350"

Test #14:

score: 6
Accepted
time: 0ms
memory: 32376kb

input:

10 2
987594303 113921174 60526162 363948313 953235693 442146116 239088362 970808700 672708631 266329194
1 7
3 1
5 1
7 3
4 3
9 5
6 5
10 7
2 7
8 4

output:

670634365

result:

ok 1 number(s): "670634365"

Test #15:

score: 6
Accepted
time: 0ms
memory: 30316kb

input:

10 3
816651453 62348752 681535935 116805607 955973251 476700964 874368097 579852140 368797919 88107985
3 8 9
2 1
4 1
10 2
3 2
7 4
5 4
9 10
8 10
6 3

output:

384680534

result:

ok 1 number(s): "384680534"

Test #16:

score: 6
Accepted
time: 3ms
memory: 30184kb

input:

10 4
58528783 12671113 11126837 192243188 969173998 711355158 552139230 134986041 320297780 856214300
4 10 2 5
6 1
9 1
2 6
4 6
5 9
8 9
3 2
10 2
7 4

output:

935582164

result:

ok 1 number(s): "935582164"

Test #17:

score: 6
Accepted
time: 0ms
memory: 32360kb

input:

10 5
918601200 505156312 418368340 295664939 184721209 379115481 848903082 880171694 194423672 240200865
3 4 10 1 9
5 1
6 1
9 5
10 5
2 6
4 6
7 9
3 9
8 10

output:

939502688

result:

ok 1 number(s): "939502688"

Test #18:

score: 0
Wrong Answer
time: 3ms
memory: 34428kb

input:

10 6
533004017 920499852 255505289 485140854 915061638 943663314 522785302 422180206 691568926 180303165
4 8 6 7 2 9
10 1
4 1
9 10
8 10
3 4
5 4
7 9
6 9
2 8

output:

417033243

result:

wrong answer 1st numbers differ - expected: '245402078', found: '417033243'

Subtask #3:

score: 0
Runtime Error

Test #43:

score: 0
Runtime Error

input:

500000 600
375999961 486674339 753591626 263678997 153496902 843204506 294273913 59353025 80121537 938426018 309354784 359915003 480316315 880954496 544396164 478808641 583197144 202111021 277512785 193266475 511298159 750302398 30978705 278891583 701736665 516664158 47658598 456194527 517690925 870...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Runtime Error

Test #77:

score: 0
Runtime Error

input:

500000 500000
200910665 704700912 664276 824905098 512233060 623259142 478040808 509760810 756074623 387351466 261683363 140331101 135736712 184881987 425557684 61914673 951508934 787260914 386285199 40458274 175322609 429002885 606957721 742057849 342942076 104844271 656874266 826513447 76400873 55...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #3:

0%