fork download 
  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <ctime>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <cctype>
  10. #include <cstdio>
  11. #include <vector>
  12. #include <cassert>
  13. #include <complex>
  14. #include <cstdlib>
  15. #include <cstring>
  16. #include <fstream>
  17. #include <iomanip>
  18. #include <sstream>
  19. #include <iostream>
  20. #include <algorithm>
  21.  
  22. using namespace std;
  23.  
  24. #define mp make_pair
  25. #define pb push_back
  26. #define ll long long
  27. #define fi first
  28. #define se second
  29.  
  30. #define all(a) a.begin(),a.end()
  31. #define fill(a,v) memset(a,v,sizeof(a))
  32.  
  33. #define bitcount __buitin_popcount
  34. #define gcd __gcd
  35.  
  36.  
  37. typedef vector<int> vi;
  38. typedef pair<int,int> pii;
  39. typedef vector<vi > vvi;
  40.  
  41. map<pii,pii> dad;
  42. map<pii,ll> rnk;
  43. void UNION(pii x,pii y)
  44. {
  45.     if(rnk[x] > rnk[y])
  46.         dad[y] = x;
  47.     else
  48.     {
  49.         dad[x] = y;
  50.         if(rnk[y] == rnk[x])
  51.             rnk[x]++;
  52.     }
  53. }
  54. pii FIND(pii x)
  55. {
  56.     if(dad[x] != x)
  57.     {
  58.         dad[x] = FIND(dad[x]);
  59.     }
  60.     else return x;
  61. }
  62. int main()
  63. {
  64.  
  65.  
  66.     ll n;
  67.     while(cin >> n)
  68.     {
  69.         if(n == -1) return 0;
  70.  
  71.         int m;cin >> m;
  72.         pii query[m];
  73.         string parity[m];
  74.  
  75.         for(int i = 0 ; i < m ; ++i)
  76.         {
  77.             cin >> query[i].fi >> query[i].se;
  78.             cin >> parity[i];
  79.         }
  80.  
  81.           int cnt = 0;
  82.          for(int i = 0 ; i < m ; ++i)
  83.          {
  84.             int x = query[i].fi,y = query[i].se;
  85.             pii s= mp(x-1,0),s1 = mp(x-1,1),d = mp(y,0),d1 = mp(y,1);
  86.             dad[s] = s;
  87.             rnk[s] = 0;
  88.             dad[s1] = s1;
  89.             rnk[s1] = 0;
  90.             dad[d] = d;rnk[d] = 0;
  91.             dad[d1] = d1;rnk[d1] = 0;
  92.          }
  93.         for(int i = 0 ; i < m ; ++i)
  94.         {
  95.             int x = query[i].fi,y = query[i].se;
  96.             pii s= mp(x-1,0),s1 = mp(x-1,1),d = mp(y,0),d1 = mp(y,1);
  97.  
  98.             if(parity[i] == "even")
  99.             {
  100.                 UNION(FIND(s),FIND(d));
  101.                 UNION(FIND(s1),FIND(d1));
  102.             }
  103.             else
  104.             {
  105.                 UNION(FIND(s1),FIND(d));
  106.                 UNION(FIND(s),FIND(d1));
  107.             }
  108.  
  109.              if(FIND(s) == FIND(s1)) goto p;
  110.              else if(FIND(d) == FIND(d1) ) goto p;
  111.              cnt++;
  112.         }
  113.  
  114.         p: cout << cnt << endl;
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0s 3304KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/rR6brj
language:
C++ (gcc 8.3)
created:
10 years 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!