QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525034#3294. 网格fanjinbo16 4ms12004kbC++142.5kb2024-08-20 11:52:342024-08-20 11:52:35

Judging History

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

  • [2024-08-20 11:52:35]
  • 评测
  • 测评结果：16
  • 用时：4ms
  • 内存：12004kb
查看
  • [2024-08-20 11:52:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ls ((now<<1))
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
const int maxn=1e5+10;
const int inf=1e9;
const int maxa=2e3+10;
const int modd=1e9+7;
#define mp make_pair
#define pii pair<int,int>
struct ji{
	int nex,to;
}edge[maxn<<5];
queue<pii>q;
map<pii,int>mat;
int t,n,m,k,x[maxn],y[maxn],tx[4]={-1,0,0,1},ty[4]={0,-1,1,0};
int V,E,head[maxn<<2],vis[maxn<<2],dfn[maxn<<2],low[maxn<<2];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void add(int x,int y){
	edge[E].nex=head[x];edge[E].to=y;head[x]=E++;
}
void dfs(int k,int fa){
	low[k]=dfn[k]=++dfn[0];
	for(int i=head[k];i!=-1;i=edge[i].nex)
		if(edge[i].to!=fa){
            if (dfn[edge[i].to])low[k]=min(low[k],dfn[edge[i].to]);
			else{
				dfs(edge[i].to,k);
				low[k]=min(low[k],low[edge[i].to]);
			}
        }	
}
int bfs(int x,int y){
	V=E=dfn[0]=0;
	q.push(mp(x,y));
	while (!q.empty()){
		x=q.front().first;
		y=q.front().second;
		q.pop();
		for(int dx=-2;dx<3;dx++)
			for(int dy=-2;dy<3;dy++){
				if ((x+dx<1)||(y+dy<1)||(x+dx>n)||(y+dy>m))continue;
				if (!mat[mp(x+dx,y+dy)]){
					mat[mp(x+dx,y+dy)]=++V;
					vis[V]=((-2<dx)&&(dx<2)&&(-2<dy)&&(dy<2));
					for(int dz=0;dz<4;dz++){
						pii o=mp(x+dx+tx[dz],y+dy+ty[dz]);
						if ((!mat[o])||(mat[o]==-2))continue;
						if (mat[o]==-1){
							mat[o]=-2;
							q.push(o);
						}else{
							add(V,mat[o]);
							add(mat[o],V);
						}
					}
				}
			}
	}
	dfs(1,0);
	if (dfn[0]<V)return 0;
	if ((vis[1])&&((head[1]==-1)||(edge[head[1]].nex==-1)))return 1;
    for(int i=2;i<=V;i++){
    	if ((vis[i])&&(low[i]==dfn[i]))return 1;
	}
    return 2;
}
int main(){
    t=read();
    while (t--){
        n=read(),m=read(),k=read();
        mat.clear();
        if (k>=1LL*n*m-1){
            for(int i=1;i<=k;i++)scanf("%*d%*d");
            cout << -1 << endl;
            continue;
        }
        memset(dfn,0,sizeof(dfn));
        memset(head,-1,sizeof(head));
        for(int i=1;i<=k;i++){
        	x[i]=read(),y[i]=read();
        	mat[mp(x[i],y[i])]=-1;
		}
		int ans=2;
        for(int i=1;i<=k;i++)
        	if (mat[mp(x[i],y[i])]==-1){
				mat[mp(x[i],y[i])]=-2;
				ans=min(ans,bfs(x[i],y[i]));
			}
		if (((n==1)||(m==1))&&(ans))ans=1;
		if ((1LL*n*m-2==k)&&(ans))ans=-1;
        cout << ans << endl;
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 4
Accepted
time: 2ms
memory: 10016kb

input:

20
1 1 0
2 1 2
1 1
2 1
1 4 2
1 4
1 1
4 1 0
2 2 2
2 2
1 1
2 1 1
1 1
3 1 0
3 1 2
3 1
2 1
2 2 2
1 2
1 1
2 2 0
1 3 3
1 2
1 1
1 3
1 3 2
1 3
1 1
2 2 1
1 2
2 2 4
2 1
1 1
2 2
1 2
1 4 2
1 2
1 4
1 1 1
1 1
4 1 1
1 1
1 4 2
1 1
1 2
1 3 1
1 2
1 2 0

output:

-1
-1
-1
1
0
-1
1
-1
-1
2
-1
-1
1
-1
0
-1
1
-1
0
-1

result:

ok 20 numbers

Test #2:

score: 4
Accepted
time: 3ms
memory: 9812kb

input:

20
2 4 8
1 4
2 4
1 2
1 3
1 1
2 2
2 1
2 3
3 2 5
1 2
1 1
2 1
3 1
3 2
8 1 8
1 1
3 1
6 1
8 1
4 1
7 1
2 1
5 1
1 8 0
4 2 7
2 1
3 2
1 1
4 1
3 1
2 2
4 2
1 7 1
1 6
4 2 4
3 1
2 2
2 1
3 2
1 8 6
1 5
1 3
1 2
1 6
1 4
1 1
2 3 1
2 2
3 2 3
1 1
1 2
3 2
1 7 6
1 4
1 3
1 1
1 2
1 6
1 5
8 1 1
1 1
2 4 6
2 4
2 1
1 1
1 2
1 4...

output:

-1
-1
-1
1
-1
0
0
-1
1
1
-1
1
-1
-1
1
1
2
0
2
-1

result:

ok 20 numbers

Test #3:

score: 0
Time Limit Exceeded

input:

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

output:

1
2
0
0
2
0
-1
1

result:

Test #4:

score: 0
Time Limit Exceeded

input:

19
5 6 2
4 4
5 2
30 1 1
11 1
5 6 6
4 3
4 2
5 6
5 1
2 3
1 5
6 5 15
4 3
3 5
4 4
6 4
2 1
5 5
1 2
2 3
6 2
5 4
4 2
4 5
3 4
2 2
5 1
4 7 10
4 3
4 1
4 4
3 4
3 3
2 1
1 3
2 5
3 7
1 1
15 2 0
9 3 2
9 1
9 2
9 3 0
7 4 3
2 1
2 3
5 3
6 5 27
1 5
1 2
2 1
2 2
5 1
3 2
3 4
5 2
5 3
6 1
4 1
1 4
2 4
6 5
2 3
3 3
5 4
4 3
6 2...

output:

1
0
1
0
1
2
2
2
1
0
2

result:

Test #5:

score: 0
Time Limit Exceeded

input:

20
10 10 35
2 2
9 2
5 6
1 9
6 3
4 6
3 6
8 4
2 4
3 9
5 10
4 9
3 4
6 2
4 10
10 5
10 7
6 1
5 8
2 6
4 5
3 1
8 1
1 2
5 4
1 4
7 1
8 10
8 2
3 7
5 9
10 1
7 4
6 9
10 3
9 11 20
6 6
8 6
4 6
7 2
3 11
1 9
1 5
4 8
2 8
6 11
9 6
8 5
1 10
6 1
6 8
7 5
7 4
7 7
5 2
2 7
10 10 100
5 6
5 5
3 3
7 3
4 2
6 6
5 1
4 7
1 5
1 1
...

output:

0
0
-1

result:

Test #6:

score: 0
Time Limit Exceeded

input:

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

output:

result:

Test #7:

score: 0
Time Limit Exceeded

input:

20
32 31 992
26 25
7 10
22 29
11 20
1 7
8 5
11 21
5 28
26 10
26 30
26 7
9 19
18 24
20 26
6 3
9 16
25 25
3 6
25 21
24 20
8 20
6 11
19 29
32 20
8 1
9 8
22 8
6 28
26 29
16 5
17 4
18 28
19 6
28 11
14 7
4 6
1 23
29 3
25 18
21 10
1 22
10 18
29 20
5 24
4 16
23 2
15 31
30 1
16 2
26 1
4 27
2 9
14 24
19 31
14...

output:

-1

result:

Test #8:

score: 0
Time Limit Exceeded

input:

20
10000 2 3
9765 1
10000 1
7719 1
400 50 5
304 15
116 23
19 10
305 15
243 37
2 10000 2
1 6458
2 2626
50 400 5
8 324
36 95
36 98
40 216
2 367
1 20000 0
100 200 5
2 1
31 84
17 194
1 199
72 52
10 2000 4
3 1090
10 1699
1 1954
7 1479
20 1000 5
12 445
16 215
19 195
19 855
1 1000
20000 1 1
3402 1
50 400 5...

output:

result:

Test #9:

score: 0
Time Limit Exceeded

input:

20
20 1000 8
15 355
10 396
2 167
18 124
2 483
2 55
19 450
1 881
50 400 10
26 22
4 25
18 134
50 315
3 281
45 49
22 248
1 81
34 355
44 50
2000 10 7
166 9
1240 4
1239 5
1132 5
1131 4
1759 5
1997 9
100 200 15
3 52
88 95
8 178
87 94
16 4
4 51
76 57
68 9
10 50
12 131
100 165
28 20
50 198
10 51
3 53
200 10...

output:

result:

Test #10:

score: 0
Time Limit Exceeded

input:

20
200 100 28
12 85
81 1
95 19
192 73
61 11
60 11
137 35
43 100
103 46
119 55
136 35
61 49
121 88
120 87
26 19
177 39
199 2
177 64
60 10
199 1
84 36
199 100
76 83
4 19
74 7
94 24
107 69
186 77
200 100 29
95 70
165 89
160 26
2 100
199 3
76 31
161 27
179 39
172 15
181 53
181 52
44 59
199 1
152 80
162 ...

output:

result:

Test #11:

score: 0
Time Limit Exceeded

input:

20
100 200 290
62 71
95 63
47 129
90 54
92 44
41 55
6 11
74 1
24 164
72 108
12 156
52 66
99 45
6 26
9 74
42 43
18 161
20 197
50 84
84 133
29 119
12 15
99 15
77 45
94 92
8 63
68 85
34 101
30 163
88 195
32 191
44 150
84 197
19 88
66 128
10 100
8 88
80 148
60 138
81 185
88 66
53 19
25 178
83 44
5 140
1...

output:

result:

Test #12:

score: 0
Time Limit Exceeded

input:

20
400 250 290
153 110
227 12
333 161
125 81
322 161
149 53
365 210
395 91
150 61
279 37
24 123
132 173
235 16
215 238
247 63
101 52
284 242
55 56
10 165
276 141
226 187
309 128
152 91
319 32
334 83
128 99
91 193
150 238
383 238
279 239
365 22
398 170
111 93
336 136
15 227
56 66
383 35
240 210
234 1...

output:

result:

Test #13:

score: 0
Time Limit Exceeded

input:

20
600 500 290
523 12
293 473
512 264
350 283
320 490
292 29
442 167
91 336
171 338
327 376
535 332
19 126
89 448
43 379
469 170
598 25
302 117
597 134
380 484
549 130
594 416
214 441
584 347
109 418
6 488
12 292
235 14
592 216
485 400
540 2
58 442
76 328
186 128
443 489
102 416
144 302
172 128
532 ...

output:

result:

Test #14:

score: 0
Time Limit Exceeded

input:

20
1000 1000 290
619 978
634 23
462 811
213 493
972 634
921 856
621 256
270 950
41 224
267 348
56 576
420 43
779 573
539 126
643 89
820 694
133 431
190 917
566 58
759 718
960 768
26 361
814 28
340 580
134 922
190 417
346 770
37 785
908 729
233 984
802 104
774 164
176 863
242 487
101 618
267 970
951 ...

output:

result:

Test #15:

score: 0
Time Limit Exceeded

input:

20
20000 20000 100
4396 15423
6910 12273
17082 16964
15130 6615
8304 5948
10882 5798
780 14436
5165 4931
3109 11062
2478 11425
4575 2057
19414 19306
4396 11278
4394 4656
4879 12273
14173 13878
17915 2601
18316 3514
11952 9185
7529 5228
1585 3769
8034 8331
387 5038
14425 5799
18835 2787
6117 7956
227...

output:

result:

Test #16:

score: 0
Time Limit Exceeded

input:

20
100000 100000 500
82912 33958
11 33879
29395 33977
43 33910
28 33936
11 33992
29357 33997
43 33898
29388 33894
82908 33946
15028 33951
15030 33940
99996 33992
33 33919
29346 33992
29365 33974
34 33880
82914 33898
33 33906
50013 33919
99997 33899
50018 33954
29355 100000
50015 33935
24 33899
4 339...

output:

result:

Test #17:

score: 4
Accepted
time: 4ms
memory: 12004kb

input:

20
1 1 0
1 1000000000 0
999999999 999999999 0
999999999 1 0
1000000000 999999999 0
1 999999999 0
2 1 0
2 999999999 0
1000000000 3 0
1000000000 1 0
2 1000000000 0
2 3 0
1000000000 2 0
1000000000 1000000000 0
999999999 1000000000 0
1 2 0
999999999 2 0
999999999 3 0
2 2 0
1 3 0

output:

-1
1
2
1
2
1
-1
2
2
1
2
2
2
2
2
-1
2
2
2
1

result:

ok 20 numbers

Test #18:

score: 4
Accepted
time: 0ms
memory: 11908kb

input:

20
1 1 1
1 1
1 5 1
1 1
999999999 1000000000 1
233 2333333
999999999 1000000000 0
2 1000000000 1
1 1
3 1 1
3 1
2 2 1
1 1
3 3 1
2 2
2 1000000000 1
1 1000000000
1000000000 1 1
2333333 1
999999999 1000000000 1
999999999 1000000000
5 5 1
3 3
1 1000000000 1
1 1000000000
3 1000000000 1
1 1
1000000000 1 0
1...

output:

-1
1
2
2
1
-1
1
2
1
0
2
2
1
2
1
-1
1
2
1
-1

result:

ok 20 numbers

Test #19:

score: 0
Time Limit Exceeded

input:

20
1 1 1
1 1
1 5 2
1 1
1 2
999999999 1000000000 2
233 2333333
1 999999999
999999999 1000000000 2
999999999 999999999
999999998 1000000000
2 1000000000 2
2 1
1 1
1 4 2
1 4
1 1
2 2 2
2 1
1 2
3 3 2
3 3
2 2
3 1000000000 2
3 33333333
2 33333333
1000000000 1 2
2333334 1
2333333 1
999999999 1000000000 2
99...

output:

-1
1

result:

Test #20:

score: 0
Time Limit Exceeded

input:

20
1000000000 999999999 3
2 1
3 1
64262205 501694537
1000000000 1000000000 3
104007914 3620272
104007912 3620271
104007913 3620271
2 2 1
2 2
2 1000000000 3
2 1
1 2
2 999999999
1 999999999 3
1 2
1 1
1 999999998
999999999 1 1
580618293 1
999999999 2 1
28331699 2
1 1000000000 3
1 999999999
1 435063528
...

output:

result:

Test #21:

score: 0
Time Limit Exceeded

input:

20
1000000000 999999999 10
829970101 672512538
829970102 672512538
349907600 671247209
261313286 745742893
637739740 496933621
997475676 80882182
637739739 496933622
123517947 242744364
263792054 171898468
637739739 496933621
2 1000000000 10
2 619577448
1 387868281
1 851264516
2 112009155
2 51967231...

output:

result:

Test #22:

score: 0
Time Limit Exceeded

input:

20
1000000000 999999999 30
900975111 554163600
371763539 17484966
775395952 16728573
200178896 33338782
376569612 878038674
936711147 663465965
257927289 27421517
627892316 696360382
936711146 663465964
925149029 126067681
521769550 733454447
931660040 659336341
185749459 541827369
42140008 71971923...

output:

result:

Test #23:

score: 0
Time Limit Exceeded

input:

20
1000000000 1000000000 300
999999977 2
999999984 9
999999968 19
999999992 1000000000
999999990 999999984
999999978 25
13 999999995
2 18
4 999999995
999999970 999999984
999999976 13
999999988 24
999999983 18
1000000000 999999989
999999984 21
6 999999980
999999968 32
999999980 999999997
999999968 99...

output:

result:

Test #24:

score: 0
Time Limit Exceeded

input:

20
1000000000 1000000000 100
347739502 476099551
999999995 476099540
347739499 476099547
1 476099558
9 476099548
1 476099549
347739506 1000000000
6 476099548
347739501 476099539
347739499 476099562
3 476099562
686950414 476099555
13 476099545
999999996 476099548
686950414 3
999999997 476099541
10000...

output:

result:

Test #25:

score: 0
Time Limit Exceeded

input:

20
1000000000 1000000000 500
16 999999942
999999945 999999976
5 999999942
12 999999984
999999931 999999951
999999969 999999999
999999938 999999974
999999941 999999989
999999958 6
999999952 999999960
9 999999938
999999963 999999936
999999998 999999971
999999931 999999940
999999960 999999923
999999965...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-11-29 23:35:43 | OpenSource Project