p12_g_parity.cpp

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define forn(i, n) for (int i = 0; i < n; ++i)
void timestamp(char const * const s, bool absolute = false);

// </template>

// <DSU>

class DSU {
private:
  int size;
  int* p;
  int* rnk;
  int* parity;
public:
  DSU(int _size) : size(_size) {
    p = new int[size];
    rnk = new int[size];
    parity = new int[size];
    forn(i, size) {
      p[i] = i;
      rnk[i] = 0;
      parity[i] = 0;
    }
  }

  ~DSU() {
    delete[] p;
    delete[] rnk;
    delete[] parity;
  }
  
  int get(int x) {
    if (p[x] == x) {
      return x;
    }
    else {
      int new_px = get(p[x]);
      parity[x] ^= parity[p[x]];
      return p[x] = new_px;
    }
  }

  void unite(int x, int y, int par) {
    int orig_x_parity = get_parity(x);
    int orig_y_parity = get_parity(y);
    x = get(x);
    y = get(y);
    // eprintf("uniting [%d←→%d], parity=%d\ninitial state: ", x, y, par);
    // eprintf_state(true);
    // eprintf("\n");
    if (rnk[x] > rnk[y]) {
      // eprintf("swapping\n");
      swap(x, y);
    }
    // eprintf("attaching %d→%d\n", x, y);
    p[x] = y;
    // eprintf("updating parity of %d from %d to %d\n", x, parity[x], parity[y] ^ par);
    parity[x] = orig_x_parity ^ par ^ orig_y_parity;
    if (rnk[x] == rnk[y]) {
      // eprintf("new rank of %d is %d\n", rnk[y], rnk[y] + 1);
      ++rnk[y];
    }
    // eprintf("final state: ");
    // eprintf_state(true);
    // eprintf("\n");
  }

  int get_parity(int x) {
    return parity[x];
  }

  void eprintf_state(bool raw = false) {
    eprintf("p=[");
    forn(i, size) {
      // eprintf("%d:%d,", i, p[i]);
      if (raw) {
        eprintf("%d,", p[i]);
      }
      else {
        eprintf("%d,", get(i));
      }
    }
    eprintf("]; parity=[");
    forn(i, size) {
      // eprintf("%d:%d,", i, parity[i]);
      if (raw) {
        eprintf("%d,", parity[i]);
      }
      else {
        eprintf("%d,", get_parity(i));
      }
    }
    eprintf("] ");
  }
};

// </DSU>

int n, m;
int t = 0;

struct Request {
  int src, dst;
  bool is_odd;
};
vector<Request> requests;

bool read() {
  cin >> n;
  if (n == -1) {
    return false;
  }
  cin >> m;

  forn(i, m) {
    int x, y;
    string s;

    cin >> x >> y >> s;

    requests.push_back(Request {x - 1, y, s == "odd"});
  }

  return true;
}

void solve() {
  unordered_map<int, int> vertices;
  for (Request& r : requests) {
    if (vertices.find(r.src) == vertices.end()) {
      vertices[r.src] = (int)vertices.size();
    }
    if (vertices.find(r.dst) == vertices.end()) {
      vertices[r.dst] = (int)vertices.size();
    }
  }

  DSU dsu((int)vertices.size() + 1);

  int error_at = m;

  // if (t >= 40) {
  //   eprintf("t=%d, n=%d, m=%d\n", t, n, m);
  // }

  forn(i, m) {
    if (error_at < i) {
      continue;
    }

    int x = vertices[requests[i].src];
    int y = vertices[requests[i].dst];
    bool is_odd = requests[i].is_odd;

    // eprintf("%d: %d→%d %d ", i, x, y, is_odd);

    if (dsu.get(x) == dsu.get(y)) {
      // eprintf("\n            ");
      // dsu.eprintf_state();
      // eprintf("\nParity of loop through [%d→%d] is %d→%d→%d\n", x, y, dsu.get_parity(x), ((int)is_odd), dsu.get_parity(y));
      int loop_parity = dsu.get_parity(x) ^ ((int)is_odd) ^ dsu.get_parity(y);
      // eprintf("L%d ", loop_parity);
      if (loop_parity == 1) {
        error_at = i;
        // eprintf("\n");
        continue;
      }
    }
    else {
      // eprintf("NL ");
      dsu.unite(x, y, is_odd);
    }

    // dsu.eprintf_state();
    // eprintf("\n");

    // forn(j, n + 1) {
    //   dsu.get(j);
    // }
  }

  // timestamp("calculating answer");

  cout << error_at << endl;

  // timestamp("writing answer");
}

void cleanup() {
  requests.clear();
  n = m = -1;
}

// <template>

void timestamp(char const * const s, bool absolute) {
  static double last = 0;
  double now = ((double)clock() / CLOCKS_PER_SEC) * 1000;
  if (absolute) {
    eprintf("%s: %.2lf ms\n", s, now);
  }
  else {
    eprintf("%s: %.2lf ms\n", s, now - last);
    last = now;
  }
}

int main() {
  timestamp("start");
  string taskname = "parity";
  string fnin = taskname + ".in";
  assert(freopen(fnin.c_str(), "r", stdin));

  timestamp("freopen()");
  for (;; ++t) {
    if (!read()) {
      break;
    }
    // timestamp("read()");
    solve();
    // timestamp("solve()");
    cleanup();
  }
  timestamp("execution");
  timestamp("total", true);
  return 0;
}