QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#663582	#9465. 基础 01 练习题	Nesraychan	0	260ms	186796kb	C++14	1.2kb	2024-10-21 16:19:11	2024-10-21 16:19:18

Judging History

你现在查看的是最新测评结果

[2024-10-21 16:19:18]
评测

测评结果：0
用时：260ms
内存：186796kb

查看

[2024-10-21 16:19:11]
提交

answer

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 200200
IL int read()
{
	reg int x=0; reg char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}

int n,q,type;
bool a[5005][5005];
std::vector<int>G[N];

IL void add(reg int u,reg int v){G[u].push_back(v);}

int dfn[N],low[N],dfc,s[N],top,scc,single;
bool in[N];

IL void cmin(reg int &x,reg int y){x>y?x=y:0;}

void tarjan(reg int u)
{
	dfn[u]=low[u]=++dfc,in[s[++top]=u]=1;
	for(auto v:G[u])
		if(!dfn[v])tarjan(v),cmin(low[u],low[v]);
		else if(in[v])cmin(low[u],dfn[v]);
	if(dfn[u]==low[u])
	{
		++scc;
		reg int cnt=0;
		do ++cnt,in[s[top]]=0; while(s[top--]!=u);
		single+=cnt==1;
	}
}

main()
{
	n=read(),q=read(),type=read();
	for(reg int i=1,lx,rx,ly,ry;i<=q;++i)
	{
		lx=read(),rx=read(),ly=read(),ry=read();
		a[lx][ly]^=1,a[rx+1][ly]^=1,a[lx][ry+1]^=1,a[rx+1][ry+1]^=1;
	}
	for(reg int i=1,j;i<=n;++i)for(j=1;j<=n;++j)a[i][j]^=a[i][j-1];
	for(reg int i=1,j;i<=n;++i)for(j=1;j<=n;++j)a[i][j]^=a[i-1][j];
	for(reg int i=1,j;i<=n;++i)for(j=1;j<=n;++j)
		if(a[i][j])add(i,j+n);
		else add(j+n,i);
	for(reg int i=1;i<=n+n;++i)if(!dfn[i])tarjan(i);
	printf("%d\n",scc-single);
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 5

Accepted

time: 0ms

memory: 11928kb

input:

output:

result:

ok 1 number(s): "1"

Test #2:

score: 5

Accepted

time: 3ms

memory: 11952kb

input:

output:

result:

ok 1 number(s): "1"

Test #3:

score: 0

Wrong Answer

time: 2ms

memory: 10104kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '5', found: '1'

Subtask #2:

score: 0

Wrong Answer

Test #4:

score: 10

Accepted

time: 7ms

memory: 11968kb

input:

50 200000 0
1 45 2 6
29 44 2 6
31 37 2 50
2 37 1 19
7 13 8 38
38 46 19 38
10 30 30 46
22 42 1 45
5 35 24 27
10 36 19 31
20 47 17 35
7 9 23 42
15 26 31 42
7 8 7 42
1 26 33 48
2 5 30 36
17 44 21 44
5 44 24 36
19 47 15 17
29 36 2 42
31 34 11 41
9 24 12 30
30 43 8 20
2 12 13 20
11 12 10 15
14 22 3 29
2 ...

output:

result:

ok 1 number(s): "1"

Test #5:

score: 0

Wrong Answer

time: 0ms

memory: 10000kb

input:

50 70 0
1 50 1 50
24 50 1 1
50 50 2 2
34 50 3 3
36 50 4 4
32 50 5 5
18 50 6 6
12 50 7 7
6 50 8 8
28 50 9 9
38 50 10 10
4 50 11 11
26 50 12 12
14 50 13 13
46 50 14 14
2 50 15 15
8 50 16 16
44 50 17 17
10 50 18 18
30 50 19 19
22 50 20 20
48 50 21 21
20 50 22 22
42 50 23 23
40 50 24 24
16 50 25 25
16 5...

output:

result:

wrong answer 1st numbers differ - expected: '2280', found: '7'

Subtask #3:

score: 0

Wrong Answer

Test #8:

score: 10

Accepted

time: 260ms

memory: 186796kb

input:

5000 200000 0
1438 2561 3478 4930
1740 4634 87 3003
590 3275 1376 1681
2035 2793 2004 4945
567 3159 550 4470
61 3039 3431 3519
2654 3834 3460 4960
591 3560 409 443
345 2599 746 2891
1288 4570 1577 4402
249 377 1951 4534
2411 2455 294 1192
1679 3153 1645 4259
1735 1856 601 668
477 4881 411 2094
424 1...

output:

result:

ok 1 number(s): "1"

Test #9:

score: 0

Wrong Answer

time: 175ms

memory: 175584kb

input:

5000 200000 0
4336 5000 1 1
686 5000 2 2
3130 5000 3 3
672 5000 4 4
1664 5000 5 5
1480 5000 6 6
1326 5000 7 7
3726 5000 8 8
4170 5000 9 9
4794 5000 10 10
3374 5000 11 11
1836 5000 12 12
310 5000 13 13
2146 5000 14 14
3266 5000 15 15
820 5000 16 16
1152 5000 17 17
2876 5000 18 18
134 5000 19 19
828 5...

output:

result:

wrong answer 1st numbers differ - expected: '24995', found: '1'

Subtask #4:

score: 0

Wrong Answer

Test #14:

score: 0

Wrong Answer

time: 237ms

memory: 185784kb

input:

5000 200000 1
565 4401 1659 1826
429 1640 2999 3495
572 3994 9 3863
3844 4284 2307 3144
1054 1943 358 2592
727 4248 29 1171
1685 2392 4559 4929
1149 2787 1204 1947
2349 2619 405 998
1910 2786 25 1275
912 3475 4384 4387
3822 4895 1849 4548
3082 4749 3457 4220
3174 4885 117 1085
2517 3919 4325 4869
17...

output:

result:

wrong answer 1st numbers differ - expected: '5000', found: '1'

Subtask #5:

score: 0

Runtime Error

Test #21:

score: 0

Runtime Error

input:

200000 200000 1
1 2 1 6
3 4 1 1
5 6 1 5
7 8 1 3
9 10 1 3
11 12 1 6
13 14 1 5
15 16 1 6
17 18 1 6
19 20 1 1
21 22 1 4
23 24 1 5
25 26 1 2
27 28 1 4
29 30 1 3
31 32 1 2
33 34 1 6
35 36 1 3
37 38 1 2
39 40 1 2
41 42 1 3
43 44 1 1
45 46 1 2
47 48 1 3
49 50 1 4
51 52 1 5
53 54 1 1
55 56 1 5
57 58 1 5
59 ...

output:

result:

Subtask #6:

score: 0

Runtime Error

Test #28:

score: 0

Runtime Error

input:

200000 200000 0
91264 123676 6826 154505
121351 188051 108158 131448
65413 163961 26771 116304
93852 110556 34929 187363
31794 142162 33578 38712
26574 67763 178013 197235
46436 146042 95 122860
11683 50463 60177 195245
60862 194711 37817 97212
144366 176271 113551 171098
120095 170517 73555 167299
...

output:

result:

Subtask #7:

score: 0

Runtime Error

Test #37:

score: 0

Runtime Error

input:

100000 200000 1
1 22878 1 2
1 7957 3 4
1 21779 5 6
1 34321 7 8
1 41692 9 10
1 49473 11 12
1 10254 13 14
1 43995 15 16
1 46975 17 18
1 668 19 20
1 25996 21 22
1 24975 23 24
1 43259 25 26
1 4174 27 28
1 39330 29 30
1 35462 31 32
1 27523 33 34
1 5574 35 36
1 47955 37 38
1 47013 39 40
1 3846 41 42
1 276...