QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334224#5372. 杀蚂蚁简单版m0NESY10 667ms6592kbC++142.0kb2024-02-21 15:07:542024-02-21 15:07:54

Judging History

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

  • [2024-02-21 15:07:54]
  • 评测
  • 测评结果:10
  • 用时:667ms
  • 内存:6592kb
  • [2024-02-21 15:07:54]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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%