Guest User

solution

a guest
Jun 6th, 2020
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #pragma comment(linker, "/stack:200000000")
  6. #pragma GCC optimize("Ofast")
  7. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  8. #pragma GCC optimize("-ffloat-store")
  9.  
  10. #define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define int long long
  12. #define endl "\n"
  13.  
  14. #define sz(a) ((int)(a).size())
  15. #define all(v) (v).begin(), (v).end()
  16. #define rall(v) (v).rbegin(), (v).rend()
  17. #define tr(c, it) for (auto it = (c).begin(); (it) != (c).end(); it++)
  18. #define pres(c, val) ((c).find(val) != (c).end())      //
  19. #define cpres(c, val) (find(all(c), val) != (c).end()) //
  20.  
  21. #define pb push_back
  22. #define mp make_pair
  23. #define F first
  24. #define S second
  25.  
  26. #define forf(i, a, b) for (int i = (a); i < (b); i++)
  27. #define forb(i, a, b) for (int i = (b); i >= (a); i--)
  28. #define fo(i, n) forf(i, 0, n)
  29. #define fob(i, n) forb(i, 0, n - 1)
  30.  
  31. typedef vector<int> vi;
  32. typedef pair<int, int> pii;
  33. typedef vector<pair<int, int>> vpii;
  34.  
  35. const int INF = 9e18;
  36. // const int N = 1e9 + 7;
  37. const int N = 998244353;
  38. const double eps = 1e-9;
  39.  
  40. const auto start_time = std::chrono::high_resolution_clock::now();
  41.  
  42. void zark() {
  43.     #ifdef ZARK
  44.         auto end_time = std::chrono::high_resolution_clock::now();
  45.         std::chrono::duration<double> diff = end_time - start_time;
  46.         cerr << "Time Taken: " << diff.count() << "s\n";
  47.     #endif
  48. }
  49.  
  50. #ifdef ZARK
  51.   #include "/home/aranjan/Desktop/CP/header.h"
  52.   #else
  53.   #define debug(args...) 42
  54. #endif
  55.  
  56. /* ------------------ Actual Coding Starts ------------------ */
  57.  
  58. map<int, int> par;
  59. map<int, int> s;
  60.  
  61. void mset(int v) {
  62.     par[v] = v;
  63.     s[v] = 1;
  64. }
  65.  
  66. int fset(int v) {
  67.     if(v == par[v]) return v;
  68.     return par[v] = fset(par[v]);
  69. }
  70.  
  71. void uset(int a, int b) {
  72.     a = fset(a);
  73.     b = fset(b);
  74.     if(a != b) {
  75.         if(s[a] < s[b]) swap(a, b);
  76.         s[a] += s[b];
  77.         par[b] = a;
  78.     }
  79. }
  80.  
  81. int off = 1e18;
  82.  
  83. void solve() {
  84.     int n,m;
  85.     cin >> n >> m;
  86.     bool f = false;
  87.     vector<pair<pii, int>> e;
  88.     int cnt = 0;
  89.     fo(i, m) {
  90.         int u, v;
  91.         string inp;
  92.         cin >> u >> v >> inp;
  93.         int c = inp == "even";
  94.         mset(u-1);
  95.         mset(v);
  96.         mset(u-1+off);
  97.         mset(v+off);
  98.         e.pb({{u, v}, c});
  99.     }
  100.     fo(i, m) {
  101.         int u=e[cnt].F.F, v=e[cnt].F.S, c=e[cnt].S;
  102.         if(u <= 0 || u > n || v <= 0 || v > n || u > v) {cout << cnt << endl; f = true; break;}
  103.         u--;
  104.         if(c) {
  105.             if(fset(u) == fset(off+v) || fset(u+off) == fset(v)) {cout << cnt << endl; f = true; break;}
  106.             else {uset(u, v); uset(off+u, off+v);}
  107.         }
  108.         else {
  109.             if(fset(u) == fset(v) || fset(u+off) == fset(v+off)) {cout << cnt << endl; f = true; break;}
  110.             else {uset(u, v+off); uset(u+off, v);}
  111.         }
  112.         cnt++;
  113.     }
  114.     if(!f) cout << cnt << endl;
  115.     int _;
  116.     cin >> _;
  117. }
  118.  
  119. int32_t main() {
  120.     fastio;
  121.     #ifdef ZARK
  122.         freopen("input.in", "r", stdin);
  123.     #endif
  124.  
  125.     // freopen("txt.in", "r", stdin);
  126.     // freopen("txt.out", "w", stdout);
  127.     // cout << fixed << setprecision(10);
  128.  
  129.     solve();
  130.     zark();
  131.     return 0;
  132. }
Add Comment
Please, Sign In to add comment