QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334243#5372. 杀蚂蚁简单版m0NESY20 1099ms8376kbC++142.3kb2024-02-21 15:54:432024-02-21 15:54:43

Judging History

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

  • [2024-02-21 15:54:43]
  • 评测
  • 测评结果:20
  • 用时:1099ms
  • 内存:8376kb
  • [2024-02-21 15:54:43]
  • 提交

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 sum=0;
        for(int i=head[u];i!=-1;i=edge[i].next)sum=(sum+v[edge[i].to])%mod;
        int c=((ll)(sum-v[fa[u]]+mod)*inv(sum)%mod+(ll)v[fa[u]]*inv(sum)%mod*f[u]%mod)%mod;
        //if(u==2)c=((ll)(sum-v[fa[u]]+mod)*inv(sum)%mod+(ll)inv(sum)*f[u]%mod)%mod;
        //else 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: 6692kb

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: 6240kb

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: 1ms
memory: 6304kb

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: 1ms
memory: 8228kb

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: 8348kb

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: 8376kb

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: 1ms
memory: 6372kb

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: 6240kb

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: 10
Accepted

Dependency #1:

100%
Accepted

Test #9:

score: 10
Accepted
time: 671ms
memory: 8272kb

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:

584487649
105375689
183540399
836906770
807065977
86021271
888605614
362898916
717572601
171877756
169742897
568399543
337164853
253104356
2092706
800994587
454522326
214671113
261859742
813312795
853226665
927653977
759323832
758339000
478192913
738386348
620107133
860692893
878764850
578900045
521...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 700ms
memory: 6324kb

input:

100
5779509 14152616 656474 8503627 14095555 11727974 12356084 1729896 17729842 7944694 16991545 6435274 9453104 8754271 5743490 2243680 14116156 292426 6706481 3977194 9849180 1233525 5188833 8191511 2476396 11502874 11589183 9997905 15553041 11398934 11239119 18625103 8278922 11603460 12388569 160...

output:

254821940
274461845
3366329
23616584
747463272
907982408
547436502
827855192
356423388
937507128
389384328
784087539
793295199
983416117
845557096
188357343
890990056
763323374
985092266
319747315
417667997
719892879
955729980
235139318
325589785
910034577
767275015
487744794
623437113
362000522
388...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 743ms
memory: 6312kb

input:

100
369779 1006956 9349847 17503913 10220636 14938645 1196297 19749049 11659785 1248372 4731829 19506662 5945083 6312396 17240491 11471094 869384 14943018 14234223 19600388 10582327 276752 6778544 4543052 7259192 14064906 9296815 19881900 12909882 15364899 3898272 8215487 1775482 13878950 1880197 19...

output:

885590350
859810213
546419053
665463385
932242241
458256389
217354939
311203856
128213507
186316281
516069217
487953875
329972875
53356533
24595074
867019881
772118045
979090003
814889925
14856253
706045800
485293200
946162740
727446250
912151961
862052232
137593129
175555537
478934634
637426584
584...

result:

ok 100000 lines

Test #12:

score: 0
Accepted
time: 781ms
memory: 8224kb

input:

100
14269305 4763951 10153534 4128997 14681370 13350972 7678806 2035272 6073698 1983526 11830927 10811443 851629 4616229 5093424 17138745 16108987 11000399 10738127 14149013 16213550 8403261 4462027 7553699 14471371 4271976 13306620 7990224 2623961 7925711 7689494 11696709 16070682 9005614 18559612 ...

output:

238919227
546470617
110117173
243195410
535688143
740799803
332584509
561109167
528357834
308131047
563457175
580343077
825634311
418130864
118830237
153792162
213724377
9326995
135506892
642632834
377526690
781036087
589856094
444234281
385790812
432719594
427508441
547234369
441263783
151801965
97...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 868ms
memory: 6548kb

input:

100
10770621 2561699 19351131 433146 11899836 19710011 5317695 15058625 5300154 17596612 12043166 5829738 3120363 3514071 16814312 19530594 14660022 5899846 11099513 172116 14587020 590635 10076972 9791472 18747501 9610051 19203373 16268716 13038618 11983064 6553183 12909635 13138335 12596489 940119...

output:

883480449
414786752
457907109
769747685
79170369
888770167
476171478
951103244
808266847
395739413
336331206
369625556
619712821
120929943
365933223
930443879
186691082
329433158
532233717
61003340
863677535
104025278
459276293
317252941
16401430
340673143
292275332
534407659
663598649
992587976
710...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 902ms
memory: 6324kb

input:

100
2643437 16727770 14160947 713726 18994986 6266026 18350691 6818112 6044848 15158147 9799251 2560223 11138435 16547487 5338010 19024010 13825652 827533 19196292 14413253 6293039 15718644 10816615 25215 15152390 8749527 11611209 7516973 170882 4665804 19624603 15502501 17554810 14938582 111986 545...

output:

426402012
331033533
308688591
144167480
127910096
113603183
257310095
976490181
300393453
733465667
618170326
231195348
870469997
894945822
585518572
970156238
150132941
373893135
719365475
466179653
750057655
906182392
804939881
659503493
481184402
173114851
675795026
156440123
821872806
506365024
...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 990ms
memory: 8352kb

input:

100
18275764 1084808 15837233 1365308 10186479 15579416 18740622 2432052 14543387 3208361 6466810 7957334 11177996 9503803 4929650 11424700 10913743 12057100 9991170 14368561 15640131 18200461 19015161 9759028 5514127 8337273 11887076 16662046 14688782 16800231 17875889 9273102 6594919 9421526 31783...

output:

209263739
401620207
765229298
564507966
382601848
776545888
806915988
112864881
421441731
171809177
606349963
526190969
570640510
167742380
707537990
975636031
515893446
409532409
872708112
943124539
358632390
417044362
730861469
782170975
406977867
813799370
556456120
95434648
561691400
329191243
1...

result:

ok 100000 lines

Test #16:

score: 0
Accepted
time: 1040ms
memory: 6376kb

input:

100
14023502 13719823 10522231 11935496 4000223 13149273 13523816 2455376 19114160 4406879 2845066 4266705 6161277 3056210 12938070 912379 9971333 11167190 3996647 952928 1360721 9957049 5249393 14915382 19506868 11714181 4664298 15558399 17192016 17332617 10590745 14090076 8733649 2826615 2761555 5...

output:

450189419
321210336
286024144
722357360
56158196
421142793
935618056
227535552
551194474
256233122
599673165
123731258
826537952
440843351
529036205
523072757
358675623
247404084
209362091
141468985
310741948
714956610
201368778
266373592
239056589
515903638
540311654
187652125
438255154
928132095
9...

result:

ok 100000 lines

Test #17:

score: 0
Accepted
time: 1099ms
memory: 6368kb

input:

100
16482998 2664429 16418531 4707794 2726207 1741400 5395305 13422883 9800377 11631446 4990276 15645985 3919273 4251552 7411366 17636710 16153505 19797882 4159429 18685297 17701050 8264546 9451462 8491704 1931109 5087368 1615209 13856566 19501977 17009797 14777967 5612495 1904651 5098283 9952660 67...

output:

447758025
425108548
475058533
47409482
108752537
793842376
869635227
109712846
649916987
262966600
4487201
56542104
353092487
692096175
292719041
663615840
333720733
11185029
166602699
635961666
746709898
980364592
487166112
865452864
278379446
790060231
879073952
612567841
561028343
187874779
23800...

result:

ok 100000 lines

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:

100%
Accepted

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%