fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e5 + 5;
  5.  
  6. long long n,q;
  7.  
  8. struct DSU
  9. {
  10.     long long lab[2*MaxN];
  11.  
  12.     void init()
  13.     {
  14.         for(long long i=0; i<=2*n+1; i++)
  15.         {
  16.             lab[i]=-1;
  17.         }
  18.     }
  19.  
  20.     long long get_root(long long u)
  21.     {
  22.         if(lab[u]<0) return u;
  23.         return lab[u]=get_root(lab[u]);
  24.     }
  25.  
  26.     void unite(long long u,long long v)
  27.     {
  28.         long long x=get_root(u);
  29.         long long y=get_root(v);
  30.  
  31.         if(x==y) return;
  32.  
  33.         if(lab[x]>lab[y]) swap(x,y);
  34.  
  35.         lab[x]+=lab[y];
  36.         lab[y]=x;
  37.     }
  38.  
  39.     bool check(long long u,long long v)
  40.     {
  41.         return get_root(u)==get_root(v);
  42.     }
  43. };
  44.  
  45. DSU dsu;
  46.  
  47. struct QUERY
  48. {
  49.     long long l,r,t;
  50. };
  51.  
  52. QUERY query[MaxN];
  53.  
  54. void input()
  55. {
  56.     cin>>n>>q;
  57.  
  58.     for(long long i=1;i<=q;i++)
  59.     {
  60.         cin>>query[i].l>>query[i].r>>query[i].t;
  61.     }
  62. }
  63.  
  64. void solve()
  65. {
  66.     long long N=n+1;
  67.  
  68.     dsu.init();
  69.  
  70.     for(long long i=1;i<=q;i++)
  71.     {
  72.         long long l=query[i].l-1;
  73.         long long r=query[i].r;
  74.         long long t=query[i].t;
  75.  
  76.         if(t==0)
  77.         {
  78.             if(dsu.check(l,r+N))
  79.             {
  80.                 cout<<i-1;
  81.                 return;
  82.             }
  83.  
  84.             dsu.unite(l,r);
  85.             dsu.unite(l+N,r+N);
  86.         }
  87.         else
  88.         {
  89.             if(dsu.check(l,r))
  90.             {
  91.                 cout<<i-1;
  92.                 return;
  93.             }
  94.  
  95.             dsu.unite(l,r+N);
  96.             dsu.unite(r,l+N);
  97.         }
  98.     }
  99.  
  100.     cout<<q;
  101. }
  102.  
  103. int main()
  104. {
  105.     ios_base::sync_with_stdio(0);
  106.     cin.tie(0);
  107.  
  108.     input();
  109.     solve();
  110. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IfS4we
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!