QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#585775 | #4889. 愚蠢的在线法官 | JZYZ | 19 | 270ms | 67840kb | C++14 | 1.7kb | 2024-09-23 22:08:13 | 2024-09-23 22:08:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int N = 5e5+10 , mod = 998244353 ;
// 又一道逆天题
// 能学到的只能说是求抽象式子时先考虑找意义
// 然后行列式的 -1 系数可以考虑交换其中两个的匹配方案,使之抵消
// (求行列式的过程可以看作两个排列进行两两匹配)
// 发现匹配竟然是唯一的,接下来dp就很简单了
int n , K , v[N] , a[N] ;
bool bt[N] ;
vector<int> E[N] ;
int tmp[N] , len ;
LL f[N][2] , g[N][3] ;//处理完子树内其他匹配方案,当前不剩/剩一个的方案
void dfs( int x , int fa )
{
for(int t : E[x] ) {
if( t == fa ) continue ;
dfs( t , x ) ;
}
if( bt[x] ) f[x][1] = 1 ;
else f[x][0] = 1 ;
len = 0 ;
tmp[++len] = x ;
for(int t : E[x] ) {
if( t == fa ) continue ;
tmp[++len] = t ;
}
// 合并
g[0][0] = 1 ;
for(int i = 1 ; i <= len ; i ++ ) {
g[i][0] = g[i-1][0] * f[tmp[i]][0] % mod ;
g[i][1] = ( g[i-1][1]*f[tmp[i]][0] + g[i-1][0]*f[tmp[i]][1] ) % mod ;
g[i][2] = ( g[i-1][2]*f[tmp[i]][0] + g[i-1][1]*f[tmp[i]][1] ) % mod ;
}
f[x][0] = ( g[len][0] + g[len][1]*(v[x]-v[fa]) ) % mod ;
f[x][1] = ( g[len][2]*(v[x]-v[fa])*2LL + g[len][1] ) % mod ;
}
int main()
{
scanf("%d%d" , &n , &K ) ;
for(int i = 1 ; i <= n ; i ++ ) scanf("%d" , &v[i] ) ;
for(int i = 1 ; i <= K ; i ++ ) {
scanf("%d" , &a[i] ) ;
if( bt[a[i]] ) { // 有重复元素,det=0
printf("0\n") ;
return 0 ;
}
bt[a[i]] = 1 ;
}
int x , y ;
for(int i = 1 ; i < n ; i ++ ) {
scanf("%d%d" , &x , &y ) ;
E[x].push_back(y) ;
E[y].push_back(x) ;
}
dfs(1,0) ;
printf("%lld" , (f[1][0]+mod)%mod ) ;
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 57ms
memory: 20204kb
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: 0ms
memory: 24296kb
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: 4ms
memory: 24296kb
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: 0
Wrong Answer
time: 0ms
memory: 22388kb
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:
759148244
result:
wrong answer 1st numbers differ - expected: '830180673', found: '759148244'
Subtask #3:
score: 0
Wrong Answer
Test #43:
score: 0
Wrong Answer
time: 247ms
memory: 47252kb
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:
745741222
result:
wrong answer 1st numbers differ - expected: '739558267', found: '745741222'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 16
Accepted
Test #77:
score: 16
Accepted
time: 270ms
memory: 46124kb
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:
771496320
result:
ok 1 number(s): "771496320"
Test #78:
score: 16
Accepted
time: 266ms
memory: 47104kb
input:
500000 500000 393325784 423307620 769839934 488701594 34980277 797798611 971252417 460892286 567253464 767364025 93413829 75786578 256363071 217722512 645295877 510711584 480877049 428293642 214340569 818013745 26677511 669553845 89063601 534123295 248791524 138950624 251295359 636455647 417371091 7...
output:
439789184
result:
ok 1 number(s): "439789184"
Test #79:
score: 16
Accepted
time: 229ms
memory: 46816kb
input:
500000 500000 304834659 23334136 281137008 195895112 196794218 9096321 550195738 251406926 794310053 392944702 896889429 377202988 383812779 855411433 996638204 176946965 14610588 31326580 287865536 285356776 15181214 721975103 7479393 923265076 700703478 244253830 13595300 191060192 506315015 82731...
output:
386763205
result:
ok 1 number(s): "386763205"
Test #80:
score: 16
Accepted
time: 246ms
memory: 67840kb
input:
500000 500000 963769621 792032953 548743692 812303224 806859822 107106153 670071669 457532666 516564922 867509289 563112863 620766458 971804950 533739313 126272905 817695615 569475276 227580608 323342974 375310982 265196242 579298928 82855065 820284887 873105018 906167288 489289717 472219706 8127735...
output:
490477004
result:
ok 1 number(s): "490477004"
Test #81:
score: 16
Accepted
time: 204ms
memory: 58296kb
input:
500000 500000 934825416 221317375 979103615 273478171 355638257 208592783 254723141 463073783 405970022 680755268 266037075 931070258 928975898 442231376 471302244 364395206 266480387 284288074 707928785 957518641 526274338 899411209 442421594 13370142 383410592 249354068 255747031 99288455 18754772...
output:
809226100
result:
ok 1 number(s): "809226100"
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #3:
0%