11121: 【原1121】二哥吵架

题目

题目描述

author: Huihuang Zheng 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1121

Description

二哥这学期和女朋友吵架变多了，女人真不好对付，这不又想出一招来对付二哥了：

石头剪刀布大家都玩过吧？

（没玩过我介绍下，玩过的跳过这段）就是石头赢剪刀，剪刀赢布，布赢石头。

但二哥妹子不跟二哥玩石头剪刀布，她打算出一种新主意：

现在二哥妹子有N种手势，以1-N编号，每个手势都是石头，剪刀，布中的一种，但她不会告诉二哥是哪一种。她会用两种方式描述给二哥听：

第一种： 1, x, y 代表x和y是同一种手势

第二种： 2，x，y 代表x赢y

二哥妹子对二哥用上面两种说法一句接一句说出K句话，当然，这个任性的家伙不会都说真话，当说的话满足下面三个条件任一时，就是假话，否则就是真话！

（1）当前话和之前说的真话冲突，就是假话，如说过2，x，y；现在又说2，y，x

（2）当前的话中x或y比N大，就是假话

（3）当前的话与石头剪刀布的规则矛盾，就是假话，如2，x，x

当不满足以上三个条件时，就认为是真话。二哥的女朋友要求二哥必须说出她讲了几句假话，这样才算了解她的心。

Input Formats

第一行，两个整数 N, K

接下来K行每行三个整数 D, X ,Y, D为1或2，代表上面的两种说法

Output Formats

只有一个整数，二哥妹子说了多少句假话

Sample Input

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

Sample Output

3

Restrictions

数据范围 1 <= N <= 100000， 0 <= K <= 100000，一切数在int型内可运算。时间限制0.5s

FineArtz's solution

/* 二哥吵架 */
#include <iostream>
using namespace std;

int n, k, ans = 0;
int op, x, y;
int p[100005], r[100005];

int parent(int x){
    if (x != p[x]){
        int t = p[x];
        p[x] = parent(p[x]);
        r[x] = (r[x] + r[t]) % 3;
    }
    return p[x];
}

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i){
        p[i] = i;
        r[i] = 0;
    }
    while (k--){
        cin >> op >> x >> y;
        if (x > n || y > n){
            ++ans;
            continue;
        }
        if (op == 2 && x == y){
            ++ans;
            continue;
        }
        int px = parent(x), py = parent(y);
        if (px == py){
            if (r[y] != (r[x] + op - 1) % 3)
                ++ans;
        }
        else{
            p[py] = px;
            r[py] = (3 - r[y] + r[x] + op - 1) % 3;
        }
    }
    cout << ans << endl;
}