QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#334224 | #5372. 杀蚂蚁简单版 | m0NESY | 10 | 667ms | 6592kb | C++14 | 2.0kb | 2024-02-21 15:07:54 | 2024-02-21 15:07:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=998244353;
inline int powmod(int a,int b){int c=1;while(b){if(b&1)c=(ll)c*a%mod;a=(ll)a*a%mod;b>>=1;}return c;}
inline int inv(int x){return powmod(x,mod-2);}
struct E{int to,next;}edge[N<<1];
int n,q,head[N],tot,v[N],du[N],fa[N],dep[N],f[N],g[N],h[N],vis[N];
vector<int> vec;
void dfs(int u,int ff)
{
if(u==2)g[u]=1;
if(u>2)
{
int x=fa[u],y=fa[x];
int p1=(ll)v[u]*inv(v[y]+v[u])%mod;
int p2=(ll)v[y]*inv(v[y]+v[u])%mod*f[x]%mod;
int p=(ll)p1*inv(1-p2+mod)%mod;
f[u]=p;
g[u]=(ll)g[fa[u]]*f[u]%mod;
}
if(u!=1)
{
int c=((ll)(du[u]-1)*inv(du[u])%mod+(ll)inv(du[u])*f[u]%mod)%mod;
h[u]=inv(1-c+mod);
}
for(int i=head[u];i!=-1;i=edge[i].next)if(edge[i].to!=ff)
fa[edge[i].to]=u,dep[edge[i].to]=dep[u]+1,dfs(edge[i].to,u);
}
inline void getpath(int u,int v)
{
vec.clear();
while(u!=v)
{
if(dep[u]>dep[v])vec.push_back(u),u=fa[u];
else if(dep[u]<dep[v])vec.push_back(v),v=fa[v];
else vec.push_back(u),u=fa[u],vec.push_back(v),v=fa[v];
}
vec.push_back(u);
}
inline void paint(int u)
{
memset(vis,0,sizeof(vis));
while(u)vis[u]=1,u=fa[u];
}
inline int calc(int u)
{
if(u==1)return 1;
int v=u;
while(!vis[v])v=fa[v];
return (ll)h[u]*g[u]%mod*inv(g[v])%mod;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
du[x]++;du[y]++;
edge[++tot]=(E){y,head[x]};head[x]=tot;
edge[++tot]=(E){x,head[y]};head[y]=tot;
}
dfs(1,0);
scanf("%d",&q);
while(q--)
{
int s,u,v;
scanf("%d%d%d",&s,&u,&v);
getpath(u,v);
paint(s);
int ans=0;
for(int i=0;i<vec.size();i++)ans=(ans+calc(vec[i]))%mod;
printf("%d\n",ans);
}
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 6248kb
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: 6312kb
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: 6244kb
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: 0ms
memory: 6592kb
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: 1ms
memory: 6324kb
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: 6240kb
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: 0ms
memory: 6396kb
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: 6304kb
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: 667ms
memory: 6400kb
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:
503045673 525741124 840131889 395137336 382279702 577920840 110150593 832461670 321160608 556682669 327204155 80258306 319552659 183266432 615238817 900622428 346657149 840983185 389710668 515982071 249074810 121916102 17865818 607849255 643240388 612049714 178337699 788973781 605884092 634546557 58...
result:
wrong answer 1st lines differ - expected: '584487649', found: '503045673'
Subtask #3:
score: 0
Time Limit Exceeded
Test #18:
score: 0
Time Limit Exceeded
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:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%