fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long 
  5. using namespace std;
  6. const long long oo=1e18;
  7. const int mod=998244353;
  8. const int base=31;
  9. const int B=320;
  10. int Test=1;
  11. void home()
  12. {
  13.     if(fopen("main.inp","r")) 
  14.     freopen("main.inp","r",stdin),
  15.     freopen("main.out","w",stdout);
  16. }
  17. bool bit(int mask,int i){return (mask>>i)&1;}
  18. struct Edge
  19. {
  20.     int u,v,w;
  21.     bool operator<(const Edge &ot)const{
  22.         return w<ot.w;
  23.     }
  24. }e[200005];
  25. struct Roll{int u,siz,w;};vector<Roll>r;
  26. int n,m;
  27. int bo[300005],sz[300005],ans=1;
  28. int Tim(int a)
  29. {
  30.     if(a==bo[a])return a;
  31.     return Tim(bo[a]);
  32. }
  33. int Hop(int u,int v,int w)
  34. {
  35.     u=Tim(u),v=Tim(v);
  36.     if(u==v)return false;
  37.     if(sz[u]<sz[v])swap(u,v);
  38.     r.push_back({u,sz[u],w});
  39.     r.push_back({v,sz[v],w});
  40.     bo[v]=u;sz[u]+=sz[v];
  41.     return true;
  42. }
  43. void RollBack(int w)
  44. {
  45.     while(r.size()&&r.back().w==w)
  46.     {
  47.         auto [u,siz,w]=r.back();r.pop_back();
  48.         bo[u]=u,sz[u]=siz;
  49.     }
  50. }
  51. int Ways(vector<Edge>&e)
  52. {
  53.     int s=e.size(),res=0,cnt=0;
  54.     for(int i=0;i<e.size();i++)if(Hop(e[i].u,e[i].v,e[i].w))cnt++;
  55.     for(int mask=0;mask<(1<<s);mask++)
  56.     {
  57.         int ok=1,used=0;
  58.         for(int i=0;i<e.size();i++)
  59.         {
  60.             if(bit(mask,i))
  61.             {
  62.                 used++;
  63.                 if(!Hop(e[i].u,e[i].v,e[i].w))ok=0;
  64.             }
  65.         }
  66.         RollBack(e[0].w);
  67.         if(ok&&cnt==used)res++;
  68.     }
  69.     for(int i=0;i<e.size();i++)Hop(e[i].u,e[i].v,e[i].w);
  70.     return res;
  71. }
  72. int Check()
  73. {
  74.     for(int i=1;i<=n;i++)if(Tim(1)!=Tim(i))return 0;
  75.     return 1;
  76. }
  77. void Tcmduc_VOI27()
  78. {
  79.     cin>>n>>m;
  80.     for(int i=1;i<=n;i++)bo[i]=i,sz[i]=1;
  81.     for(int i=1;i<=m;i++)
  82.     {
  83.         int u,v,w;cin>>u>>v>>w;
  84.         e[i]={u,v,w};
  85.     }
  86.     sort(e+1,e+m+1);
  87.     for(int i=1;i<=m;)
  88.     {
  89.         int j=i;vector<Edge>cur;
  90.         for(;j<=m;j++)
  91.         {
  92.             if(e[i].w!=e[j].w)break;
  93.             cur.push_back(e[j]);
  94.         }
  95.         ans=(ans*Ways(cur))%mod;
  96.         i=j;
  97.     }
  98.     if(!Check())cout<<0;
  99.     else cout<<ans;
  100. }
  101. signed main()
  102. {
  103.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  104.     while(Test--)Tcmduc_VOI27();
  105.     return 0;
  106. }
Success #stdin #stdout 0s 5656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/TyhOmI
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!