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,id;
  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[300005];
  28. vector<pair<int,int>>a[300005];
  29. int Tim(int a)
  30. {
  31.     if(a==bo[a])return a;
  32.     return bo[a]=Tim(bo[a]);
  33. }
  34. int Hop(int u,int v)
  35. {
  36.     u=Tim(u),v=Tim(v);
  37.     if(u==v)return false;
  38.     if(sz[u]<sz[v])swap(u,v);
  39.     bo[v]=u;sz[u]+=sz[v];
  40.     return true;
  41. }
  42. int num[300005],low[300005];
  43. int timer=0;
  44. void DFS(int u,int pId)
  45. {
  46.     low[u]=num[u]=++timer;
  47.     for(auto [v,id]:a[u])
  48.     {
  49.         if(id==pId)continue;
  50.         if(!num[v])
  51.         {
  52.             DFS(v,id);
  53.             low[u]=min(low[u],low[v]);
  54.             if(low[v]>num[u])ans[id]=1;
  55.         }
  56.         else low[u]=min(low[u],num[v]);
  57.     }
  58. }
  59. void Tcmduc_VOI27()
  60. {
  61.     cin>>n>>m;
  62.     for(int i=1;i<=n;i++)bo[i]=i,sz[i]=1;
  63.     for(int i=1;i<=m;i++)
  64.     {
  65.         int u,v,w;cin>>u>>v>>w;
  66.         e[i]={u,v,w,i};
  67.     }
  68.     sort(e+1,e+m+1);
  69.     for(int i=1;i<=m;)
  70.     {
  71.         int j=i;vector<int>p;
  72.         for(;j<=m;j++)
  73.         {
  74.             auto [u,v,w,id]=e[j];
  75.             if(e[i].w!=w)break;
  76.             if(Tim(u)!=Tim(v))
  77.             {
  78.                 u=Tim(u),v=Tim(v);
  79.                 p.push_back(u);p.push_back(v);
  80.                 a[u].push_back({v,id});
  81.                 a[v].push_back({u,id});
  82.             }
  83.             else ans[id]=0;
  84.         }
  85.         timer=0;
  86.         for(int u:p)if(!num[u])DFS(u,0);
  87.         for(int u:p)
  88.         {
  89.             num[u]=low[u]=0;
  90.             a[u].clear();
  91.         }
  92.         for(;i<j;i++)Hop(e[i].u,e[i].v);
  93.     }
  94.     for(int i=1;i<=m;i++)
  95.     {
  96.         if(ans[i])cout<<"Yes"<<' ';
  97.         else cout<<"No"<<' ';
  98.     }
  99. }
  100. signed main()
  101. {
  102.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  103.     while(Test--)Tcmduc_VOI27();
  104.     return 0;
  105. }
Success #stdin #stdout 0.01s 15780KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/toko9w
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!