QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#346468 | #4889. 愚蠢的在线法官 | zzafanti | 0 | 1ms | 3708kb | C++20 | 2.1kb | 2024-03-08 15:51:55 | 2024-03-08 15:51:55 |
answer
#include<bits/stdc++.h>
using namespace std;
using E=long long;
constexpr E mod=998244353;
vector<int> vis,v,fa,sz;
vector<vector<int>> ver;
vector<vector<E>> dp;
E n,k;
void dfs(int u){
dp[u][0]=1;
if(vis[u]) sz[u]=1;
for(auto p:ver[u]){
if(p==fa[u]) continue;
fa[p]=u;
dfs(p);
sz[u]+=sz[p];
}
dp[u][1]=(dp[u][1]+sz[u]*(v[u]-v[fa[u]]+mod))%mod;
for(auto p:ver[u]){
if(p==fa[u]) continue;
for(int i=k; i>1; i--){
E t=dp[p][i];
for(int j=0; j<i-1; j++){
t=(t+dp[u][i-j]*dp[p][j])%mod;
}
t=(t+(dp[u][1]-sz[p]*(v[u]-v[fa[u]]+mod)%mod+mod)*dp[p][i-1])%mod;
dp[u][i]=t;
}
dp[u][1]=(dp[u][1]+dp[p][1])%mod;
}
}
vector<int> dep,dfn;
int timestamp;
void dfs0(int u){
dfn[u]=++timestamp;
for(auto p:ver[u]){
if(fa[u]==p) continue;
fa[p]=u;
dep[p]=dep[u]+1;
dfs0(p);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=fa[x];
while(x!=y) x=fa[x],y=fa[y];
return x;
}
int main(){
#ifdef zzafanti
freopen("in.in","r",stdin);
#endif // zzafanti
cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k;
dp=vector<vector<E>>(n+1,vector<E>(k+1));
ver.resize(n+1);
sz=dfn=dep=fa=vis=v=vector<int>(n+1);
for(int i=1; i<=n; i++) cin>>v[i];
for(int i=1; i<=k; i++){
int a;
cin>>a;
vis[a]++;
}
for(int i=1; i<n; i++){
int x,y;
cin>>x>>y;
ver[x].emplace_back(y);
ver[y].emplace_back(x);
}
for(int i=1; i<=n; i++){
if(vis[i]>1){
cout<<0;
return 0;
}
}
dfs0(1);
dfs(1);
cout<<dp[1][k]<<endl;
return 0;
vector<int> A,B;
for(int i=1; i<=n; i++){
A.emplace_back(i);
if(vis[i]) B.emplace_back(i);
}
sort(A.begin(),A.end(),[&](int x,int y){ return dfn[x]<dfn[y]; });
sort(B.begin(),B.end(),[&](int x,int y){ return dfn[x]<dfn[y]; });
cerr<<0<<' ';
for(auto i:A) cerr<<i<<' ';
cerr<<endl;
for(auto i:B){
cerr<<i<<' ';
for(auto j:A){
cerr<<(lca(i,j)==j)<<' ';
}
cerr<<endl;
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
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:
result:
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 6
Accepted
time: 1ms
memory: 3708kb
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
Wrong Answer
time: 1ms
memory: 3500kb
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:
345316084
result:
wrong answer 1st numbers differ - expected: '816324383', found: '345316084'
Subtask #3:
score: 0
Time Limit Exceeded
Test #43:
score: 0
Time Limit Exceeded
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
Memory Limit Exceeded
Test #77:
score: 0
Memory Limit Exceeded
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:
0%