1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
const int N = 500005;
int pre[N], ran[N];
int m,n;
void init()
{
for (int i = 1; i <= m;i++)
{
pre[i] = i;
ran[i] = 0;
}
}
int find(int x)
{
if(x==pre[x])
return pre[x];
int f = find(pre[x]);
ran[x] = (ran[pre[x]] + ran[x]+3) % 3;
return pre[x] = f;
}
bool pan(int d,int a,int b)
{
if(a>m||b>m||(d==2&&a==b))
return 0;
int fx = find(a);
int fy = find(b);
if(fx==fy)
{
if((ran[a]-ran[b]+3)%3==(d-1)) return 1;
else return 0;
}
else return 1;
}
void un(int d,int a,int b)
{
int fx = find(a);
int fy = find(b);
if(fx!=fy)
{
ran[fx] = (ran[b] - ran[a] + d+3) % 3;
pre[fx] = fy;
}
}
int main()
{
scanf("%d%d", &m, &n);
for(int i=0; i<=m; i++) { pre[i]=i; ran[i]=0; }
int joke=0;
int e1, e2, e3;
while(n--)
{
scanf("%d%d%d", &e1, &e2, &e3);
if( !pan(e1, e2, e3) ) joke++;
else un(e1-1, e2, e3);
}
printf("%dn", joke);
return 0;
}
|
近期评论