QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783803#8078. Spanning Treefsdhmbb#WA 79ms45200kbC++141.9kb2024-11-26 11:50:372024-11-26 11:50:47

Judging History

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

  • [2024-11-26 11:50:47]
  • 评测
  • 测评结果:WA
  • 用时:79ms
  • 内存:45200kb
  • [2024-11-26 11:50:37]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int mod=998244353;
vector <int> mp[maxn];
int l[maxn],r[maxn];
int fa[maxn],siz[maxn];
long long a,b,p;
long long quickPower(long long a,long long b,long long p)
{
    long long ans=1,base=a;
    while (b>0)
    {
        if(b&1==1){
            ans*=base;
            ans%=p;
        }
        base*=base;
        base%=p;
        b>>=1;
    }
    return ans;
}
void dfs(int u,int f)
{
    fa[u]=f;
    for(auto v:mp[u])
    {
        if(v!=f)
        {
            dfs(v,u);
        }
    }
}
struct BCJ
{
    int fa[maxn];
    void init(int n)
    {
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
            siz[i]=1;
        }
    }
    int findfa(int x)
    {
        if(x==fa[x])
        {
            return x; 
        }
        return fa[x]=findfa(fa[x]);
    }
    void merge(int a,int b)
    {
        fa[a]=findfa(b);
        siz[b]+=siz[a];
    }
}bcj;
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>l[i]>>r[i];
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    bcj.init(n);
    dfs(1,1);
    int cnt=1;
    for(int i=1;i<n;i++)
    {
        if(bcj.findfa(l[i])==bcj.findfa(r[i]))
        {
            cout<<"0\n";
            return 0;
        }
        if((bcj.findfa(fa[bcj.findfa(l[i])])==bcj.findfa(r[i]))||(bcj.findfa(fa[bcj.findfa(r[i])])==bcj.findfa(l[i])))
        {
            cnt=cnt*siz[bcj.findfa(l[i])]%mod*siz[bcj.findfa(r[i])]%mod;
            bcj.merge(bcj.findfa(l[i]),bcj.findfa(r[i]));
        }   
        else 
        {
            cout<<"0\n";
            return 0;
        }
    }
    //cout<<cnt<<"\n";
    cout<<quickPower(cnt,mod-2,mod)<<"\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 36824kb

input:

3
1 2
1 3
1 2
1 3

output:

499122177

result:

ok single line: '499122177'

Test #2:

score: -100
Wrong Answer
time: 79ms
memory: 45200kb

input:

100000
2183 5543
22424 59062
8387 24544
14668 74754
15788 58136
26846 99981
13646 57752
29585 62862
27383 65052
2013 13116
24490 91945
26006 61595
19000 78817
31371 67837
29311 82989
4298 20577
23212 77962
16510 85839
26010 98714
25314 96063
17206 82359
7478 76540
13890 99556
23277 64321
25684 92613...

output:

0

result:

wrong answer 1st lines differ - expected: '330864231', found: '0'