UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197434#3447. 远恋shiruiheng100645ms11384kbC++111.3kb2023-11-12 09:40:362023-11-12 13:13:55

answer

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n, q, op[100010], x[100010], y[100010], d[100010], ans[100010];
map<pair<int, int>, int> mp;
/*
ll fa[100010], ans1, cnt[100010];
int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int a, int b){
	int fx = find(a), fy = find(b);
	if(fx == fy)
		return;
	if(cnt[fx] > cnt[fy])
		swap(fx, fy);
	cnt[fy] += (cnt[fx] == cnt[fy]);
	fa[fx] = fy;
}
//*/
signed main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1 ; i <= q ; i++){
    	scanf("%d%d%d", op + i, x + i, y + i);
    	if(y[i] > x[i])
    		swap(x[i], y[i]);
    	op[i] %= 2;
    	if(op[i] == mp[{x[i], y[i]}]){
    		ans[i] = ans[i - 1];
		}
		else{
    		mp[{x[i], y[i]}] = op[i];
    		if(op[i] == 0){
    			if(d[x[i]] == 1 && d[y[i]] == 1)
    				ans[i] = ans[i - 1] - 1;
    			else if(d[x[i]] == 1 || d[y[i]] == 1)
    				ans[i] = ans[i - 1];
    			else
    				ans[i] = ans[i - 1] + 1;
    			d[x[i]]--;
    			d[y[i]]--;
			}
			else{
				if(d[x[i]] == 0 && d[y[i]] == 0)
					ans[i] = ans[i - 1] + 1;
				else if(d[x[i]] == 0 || d[y[i]] == 0)
					ans[i] = ans[i - 1];
				else
					ans[i] = ans[i - 1] - 1;
				d[x[i]]++;
				d[y[i]]++;
			}
		}
		printf("%d\n", ans[i]);
	}
    exit(0);
}
/*
*/
源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 52ms
memory: 4356kb

input:

2 100000
1 2 1
2 1 2
1 1 2
1 1 2
1 2 1
2 2 1
2 2 1
2 1 2
2 2 1
2 1 2
1 1 2
2 1 2
2 1 2
2 2 1
1 2 1
1...

output:

1
0
1
1
1
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
1
1
1
0
1
1
0
0
1
0
0
0
0
1
0
1
1
1
1
0
0
0
0
1
0
0
0
1
0
1
...

result:

ok 100000 numbers

Test #2:

score: 10
Accepted
time: 40ms
memory: 4356kb

input:

2 100000
2 1 2
2 1 2
2 2 1
2 2 1
1 1 2
1 1 2
1 1 2
1 2 1
2 1 2
1 1 2
2 2 1
2 1 2
2 2 1
2 1 2
2 2 1
2...

output:

0
0
0
0
1
1
1
1
0
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
1
0
1
0
0
1
1
1
1
0
0
1
0
1
1
1
1
0
1
1
1
1
1
0
1
0
...

result:

ok 100000 numbers

Test #3:

score: 10
Accepted
time: 0ms
memory: 1444kb

input:

2000 2000
1 964 329
2 1284 1313
1 787 509
2 945 658
1 1053 1194
1 1964 1595
2 1504 1111
2 1425 469
2...

output:

1
1
2
2
3
4
4
4
4
5
5
6
6
7
8
9
10
11
12
12
13
14
15
16
17
17
18
19
20
20
20
21
21
22
22
23
23
23
24...

result:

ok 2000 numbers

Test #4:

score: 10
Accepted
time: 0ms
memory: 1448kb

input:

2000 2000
2 315 602
1 649 1798
2 26 785
1 586 1610
2 1854 883
1 1861 622
2 756 1668
2 687 98
2 1619 ...

output:

0
1
1
2
2
3
3
3
3
4
5
6
6
7
8
9
10
11
11
12
12
13
14
15
16
16
16
16
16
16
16
17
18
18
19
20
21
22
23...

result:

ok 2000 numbers

Test #5:

score: 10
Accepted
time: 3ms
memory: 2204kb

input:

100000 2000
1 92779 34174
2 24442 50350
2 95908 70204
1 24040 90714
1 72654 11859
2 92767 96242
1 72...

output:

1
1
1
2
3
3
4
4
5
5
6
6
7
8
8
9
9
10
11
11
12
12
13
13
14
15
15
15
16
17
17
18
19
20
20
20
20
20
21
...

result:

ok 2000 numbers

Test #6:

score: 10
Accepted
time: 2ms
memory: 2208kb

input:

100000 2000
2 51154 58009
2 60818 30639
1 19247 71910
2 14664 29829
1 4253 44694
1 32318 94691
2 939...

output:

0
0
1
1
2
3
3
4
4
5
6
7
7
7
7
8
8
9
10
11
11
11
12
13
13
14
15
15
16
16
17
18
18
18
19
19
20
20
20
2...

result:

ok 2000 numbers

Test #7:

score: 10
Accepted
time: 155ms
memory: 11384kb

input:

100000 99999
1 83203 7892
1 89609 30806
1 17204 58475
1 94078 40656
1 12175 54519
1 96583 57951
1 64...

output:

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
3...

result:

ok 99999 numbers

Test #8:

score: 10
Accepted
time: 109ms
memory: 11384kb

input:

100000 99999
1 60027 76791
1 94226 32512
1 43832 3682
1 52120 92287
1 39908 42152
1 29887 44511
1 74...

output:

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
3...

result:

ok 99999 numbers

Test #9:

score: 10
Accepted
time: 132ms
memory: 11380kb

input:

100000 100000
2 74884 54626
2 10396 73081
1 18384 59139
1 48884 27924
1 2340 74923
2 38603 14867
1 9...

output:

0
0
1
2
3
3
4
4
4
4
4
4
4
4
4
5
5
6
7
7
8
8
9
9
9
9
9
10
11
11
11
11
11
11
12
13
13
14
15
15
16
16
1...

result:

ok 100000 numbers

Test #10:

score: 10
Accepted
time: 152ms
memory: 11380kb

input:

100000 100000
1 68584 71139
1 62909 25950
1 81680 54537
1 25264 95674
1 16361 23965
1 81367 39665
1 ...

output:

1
2
3
4
5
6
7
8
9
9
10
10
10
11
11
11
11
12
13
13
14
14
15
15
15
16
17
18
18
18
19
20
20
20
20
20
20...

result:

ok 100000 numbers

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-03-06 11:45:47 | 开源项目