#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef set<int> NSet;
static vector<NSet> sets;
static map<int, int> vertex_mapping;
static vector<int> unused_set_num;
static vector<int> set_mapping;
static vector<int> conflict_sets;
/*----------- manages the value to vertex index mapping -----------*/
static int get_vertex_num(int a)
{
if (vertex_mapping.find(a) == vertex_mapping.end()) {
int new_num = vertex_mapping.size();
vertex_mapping.insert(make_pair(a, new_num));
return new_num;
}
return vertex_mapping[a];
}
/*----------- manages the set number assignment---------*/
static int allocateNewSetNum()
{
int num = unused_set_num[unused_set_num.size() - 1];
unused_set_num.pop_back();
return num;
}
static void freeSetNum(int num)
{
unused_set_num.push_back(num);
conflict_sets[num] = -1;
}
/*---------- set operations ----------------*/
static int assignNewSet(int va)
{
int set_num = allocateNewSetNum();
/** allocate an empty conflict set, this would simplify
* the operations */
int conflict_num = allocateNewSetNum();
conflict_sets[set_num] = conflict_num;
conflict_sets[conflict_num] = set_num;
sets[set_num].insert(va);
return set_num;
}
static NSet& get_set(int va)
{
int& set_num = set_mapping[va];
if (set_num == -1)
set_num = assignNewSet(va);
return sets[set_num];
}
static int get_set_num(int va)
{
int& set_num = set_mapping[va];
if (set_num == -1)
set_num = assignNewSet(va);
return set_num;
}
static NSet& get_conflict_set(int va)
{
int& set_num = set_mapping[va];
if (set_num == -1)
set_num = assignNewSet(va);
return sets[conflict_sets[set_num]];
}
static int get_conflict_set_num(int va)
{
int& set_num = set_mapping[va];
if (set_num == -1)
set_num = assignNewSet(va);
return conflict_sets[set_num];
}
/* semantic of merging two sets, merge s2 to s1 */
static void doMerge(NSet& s1, int set_num1, NSet& s2, int set_num2)
{
for (NSet::iterator it2 = s2.begin();
it2 != s2.end(); ++it2) {
if (s1.find(*it2) == s1.end()) {
s1.insert(*it2);
set_mapping[*it2] = set_num1;
}
}
s2.clear();
freeSetNum(set_num2);
}
static void dumpSet(NSet& s, int set_num)
{
printf("set %d\n", set_num);
for (NSet::iterator sit = s.begin(); sit != s.end();
++sit) {
printf("%d ", *sit);
}
printf("\nconflict set is %d\n", conflict_sets[set_num]);
}
static void dumpAll()
{
printf("vertex mapping\n");
for (map<int,int>::iterator vit = vertex_mapping.begin();
vit != vertex_mapping.end(); ++vit) {
printf("val %d is vertex %d\n", vit->first, vit->second);
printf("vertex %d maps to set %d\n", vit->second, set_mapping[vit->second]);
}
for (int i = 0; i < sets.size(); i++) {
dumpSet(sets[i], i);
}
}
/*----------- judge the conflict condition --------------*/
static int insertSegment(int a, int b, bool conflict)
{
int va = get_vertex_num(a);
int vb = get_vertex_num(b);
int nsa = get_set_num(va);
int nsb = get_set_num(vb);
if (nsa == nsb) return conflict? -1: 0;
int nca = get_conflict_set_num(va);
int ncb = get_conflict_set_num(vb);
if (nsa == ncb) return conflict? 0: -1;
NSet& sa = get_set(va);
NSet& sb = get_set(vb);
NSet& ca = get_conflict_set(va);
NSet& cb = get_conflict_set(vb);
if (conflict) {
if (sa.find(vb) != sa.end())
return -1;
doMerge(sa, nsa, cb, ncb);
doMerge(sb, nsb, ca, nca);
conflict_sets[nsa] = nsb;
conflict_sets[nsb] = nsa;
} else {
if (ca.find(vb) != ca.end())
return -1;
doMerge(sa, nsa, sb, nsb);
doMerge(ca, nca, cb, ncb);
}
return 0;
}
static void initStruct(int N)
{
/** initialize the set number list */
for (int i = 0; i < 4 * N; i++)
unused_set_num.push_back(i);
fill_n(back_inserter(set_mapping), 2 * N, -1);
/* each set corresponds to a conflict set */
fill_n(back_inserter(sets), 4 * N, NSet());
fill_n(back_inserter(conflict_sets), 4 * N, -1);
}
static void solve(int N)
{
for (int i = 0; i < N; i++) {
int a, b, ret;
/** BUG: suffers from overflow. Just for convenience */
char condition[100];
scanf("%d%d%s", &a, &b, condition);
if (strcmp(condition, "even") == 0)
ret = insertSegment(a, b + 1, false);
else
ret = insertSegment(a, b + 1, true);
//dumpAll();
if (ret == -1) {
printf("%d\n", i);
return;
}
}
printf("%d\n", N);
}
int main()
{
int N;
scanf("%*d%d", &N);
initStruct(N);
solve(N);
return 0;
}
|