QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#144527#6503. DFS Order 3qzhwlzyWA 122ms7644kbC++141.4kb2023-08-21 16:53:562023-08-21 16:53:59

Judging History

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

  • [2023-08-21 16:53:59]
  • 评测
  • 测评结果：WA
  • 用时：122ms
  • 内存：7644kb
查看
  • [2023-08-21 16:53:56]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<queue>
#define maxn 1005
using namespace std;
int T,n,a[maxn][maxn],cnt; queue<int> q; bool leaf[maxn],vis[maxn],vvis[maxn]; int fa[maxn];
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
void unionn(int p1,int p2){int r1=findfa(p1),r2=findfa(p2); if(r1!=r2) fa[r1]=r2;}
void set(){for(int i=1;i<=n;i++) a[i][0]=2,leaf[i]=vvis[i]=0,fa[i]=i; while(!q.empty()) q.pop(); cnt=0;}
int findnex(int p){
	for(;a[p][0]<=n;a[p][0]++) if(!leaf[a[p][a[p][0]]]&&findfa(p)!=findfa(a[p][a[p][0]])) return a[p][a[p][0]];
	else if(!leaf[a[p][a[p][0]]]) return 0; return 0;
}
void dfs(int p){
	int nxt=findnex(p); if(nxt==0) return; printf("%d %d\n",p,nxt); cnt++; unionn(p,nxt); vis[nxt]=1;
	if(cnt==n-1) return; dfs(nxt);
}
int main(){
	scanf("%d",&T); while(T--){
		scanf("%d",&n); set(); for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); a[i][n+1]=n;}
		for(int i=1;i<=n;i++) if(!vvis[a[i][n]]) q.push(a[i][n]),vvis[a[i][n]]=1;
		while(cnt!=n-1){
			int top=q.front(); q.pop(); leaf[top]=vis[top]=1; dfs(top); if(cnt==n-1) break;
			for(int i=1;i<=n;i++){
				while(leaf[a[i][a[i][n+1]]]) a[i][n+1]--; a[i][n+1]++;
				if(leaf[a[i][a[i][n+1]]]&&!vvis[a[i][a[i][n+1]-1]])
					q.push(a[i][a[i][n+1]-1]),vvis[a[i][a[i][n+1]-1]]=1,a[i][n+1]--;
			}	
			if(q.empty()&&cnt!=n-1) for(int i=1;i<=n;i++) if(vis[i]&&!vvis[i]) q.push(i),vvis[i]=1;
		}
	}
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5864kb

input:

4
2
1 2
2 1
3
1 2 3
2 1 3
3 2 1
4
1 2 3 4
2 1 3 4
3 2 4 1
4 2 1 3
5
1 2 4 3 5
2 4 1 3 5
3 5 1 2 4
4 2 1 3 5
5 3 1 2 4

output:

2 1
3 2
2 1
4 2
2 1
3 2
5 3
3 1
1 2
2 4

result:

ok correct answer! (4 test cases)

Test #2:

score: 0
Accepted
time: 111ms
memory: 3748kb

input:

20000
10
1 2 4 5 6 7 3 8 10 9
2 1 4 5 6 7 3 8 10 9
3 8 1 2 4 5 6 7 10 9
4 5 6 7 1 2 3 8 10 9
5 4 6 7 1 2 3 8 10 9
6 7 4 5 1 2 3 8 10 9
7 6 4 5 1 2 3 8 10 9
8 3 1 2 4 5 6 7 10 9
9 10 1 2 4 5 6 7 3 8
10 1 2 4 5 6 7 3 8 9
10
1 4 3 8 2 9 6 5 7 10
2 8 9 6 3 4 1 5 7 10
3 8 2 9 6 4 1 5 7 10
4 1 3 8 2 9 6 5...

output:

9 10
10 1
1 2
8 3
3 1
7 6
6 4
4 5
1 4
10 7
7 5
5 4
4 1
6 9
9 8
8 2
8 3
3 4
4 2
2 8
7 5
5 6
8 10
10 3
10 9
9 1
5 9
4 2
2 10
9 6
6 1
10 6
3 8
8 7
7 5
6 7
2 10
10 3
3 6
8 9
9 1
3 7
7 4
1 5
5 7
7 9
9 8
8 3
2 6
6 10
10 1
4 8
8 10
5 10
9 2
2 3
3 7
7 6
1 10
10 2
4 8
8 5
5 7
5 10
10 9
9 1
1 4
4 2
2 3
8 4
6 ...

result:

ok correct answer! (20000 test cases)

Test #3:

score: 0
Accepted
time: 101ms
memory: 4092kb

input:

200
100
1 51 45 20 15 66 21 71 83 29 77 70 82 46 79 47 17 50 38 85 69 35 14 60 44 11 36 86 28 58 89 61 34 7 92 39 59 94 63 75 12 81 16 6 23 37 74 52 42 13 65 91 57 40 62 93 72 96 68 26 78 84 43 10 9 33 56 87 97 27 22 80 55 24 98 76 3 18 48 90 64 49 67 4 19 53 32 54 73 8 31 88 99 25 100 5 2 41 95 30
...

output:

30 95
95 5
5 2
25 99
99 90
90 64
41 5
5 100
100 3
3 68
68 40
40 91
91 57
76 98
98 24
88 73
73 8
31 73
24 80
80 55
73 49
49 67
67 4
4 19
80 22
22 26
26 78
54 32
32 53
27 97
97 56
56 87
53 4
56 33
33 9
49 90
9 10
10 43
90 18
18 48
43 84
84 26
18 3
26 68
96 72
72 93
75 94
94 63
93 62
62 40
94 47
47 79
...

result:

ok correct answer! (200 test cases)

Test #4:

score: 0
Accepted
time: 95ms
memory: 6468kb

input:

8
500
1 164 494 392 66 328 402 15 156 395 234 78 241 304 4 54 439 387 83 460 220 490 369 343 172 190 108 122 173 384 290 403 231 254 70 29 294 359 153 59 228 474 167 222 491 357 169 383 50 103 447 84 344 237 376 457 238 17 363 131 34 244 472 104 154 322 140 488 193 390 245 147 31 189 191 221 259 456...

output:

239 500
500 65
65 208
208 5
5 124
124 143
143 168
168 209
207 499
499 152
152 253
152 158
158 157
157 35
35 341
279 168
400 319
319 58
319 300
300 35
124 227
227 327
436 289
289 210
289 416
416 227
157 25
25 82
82 497
497 463
227 408
408 399
399 144
496 136
136 414
414 48
48 92
497 324
324 483
133 4...

result:

ok correct answer! (8 test cases)

Test #5:

score: 0
Accepted
time: 81ms
memory: 7640kb

input:

2
1000
1 586 727 909 178 211 319 562 12 759 714 885 988 612 507 670 288 932 608 333 649 663 14 826 874 930 968 965 780 353 558 76 787 617 815 181 31 552 3 761 398 814 740 841 789 282 636 894 179 569 566 408 225 334 671 294 101 634 218 270 412 463 400 495 804 710 262 93 572 18 673 808 862 711 350 603...

output:

1000 775
775 993
993 827
266 685
685 394
394 735
735 999
993 103
103 665
665 893
893 116
116 106
999 137
137 197
197 625
625 785
785 637
480 887
887 116
991 355
355 94
94 614
737 116
94 668
668 416
416 565
565 600
600 253
253 702
702 570
665 888
888 38
967 726
726 425
425 950
950 765
765 395
395 557...

result:

ok correct answer! (2 test cases)

Test #6:

score: 0
Accepted
time: 122ms
memory: 3748kb

input:

20000
10
1 5 6 9 8 2 3 4 10 7
2 3 8 9 4 10 7 5 1 6
3 2 8 9 4 10 7 5 1 6
4 9 5 1 6 8 2 3 10 7
5 1 6 9 4 10 7 8 2 3
6 5 1 9 4 10 7 8 2 3
7 10 4 9 5 1 6 8 2 3
8 2 3 9 4 10 7 5 1 6
9 4 10 7 5 1 6 8 2 3
10 4 9 5 1 6 8 2 3 7
10
1 3 6 5 2 9 4 7 8 10
2 3 1 6 5 9 4 7 8 10
3 1 2 9 4 7 8 10 6 5
4 7 8 9 2 3 1 6...

output:

7 10
10 4
4 9
6 5
5 1
3 2
2 8
8 9
9 5
10 9
9 2
2 3
3 1
5 6
6 3
8 4
4 7
4 9
10 9
9 3
3 4
4 2
2 1
1 5
8 6
6 3
7 9
9 10
10 2
2 7
7 1
8 3
3 5
4 6
6 3
3 7
9 7
7 2
8 1
1 6
4 10
10 3
3 7
1 5
5 10
10 8
8 9
9 3
3 1
1 4
7 5
5 9
6 3
2 3
10 4
4 8
8 2
2 6
6 1
1 7
9 2
5 7
3 8
8 10
10 7
7 6
6 1
1 5
4 5
2 3
3 5
9 7...

result:

ok correct answer! (20000 test cases)

Test #7:

score: 0
Accepted
time: 100ms
memory: 4116kb

input:

200
100
1 33 31 11 2 28 44 79 34 96 55 18 49 86 87 23 29 62 47 61 92 89 26 72 22 90 85 57 91 67 95 14 5 64 43 71 30 15 78 3 52 60 97 21 80 53 27 56 7 25 42 13 63 59 65 82 83 75 16 77 69 20 99 32 70 46 24 94 54 17 58 68 98 48 37 12 38 66 6 88 84 35 50 74 73 39 81 8 19 4 76 9 10 45 93 41 51 40 36 100
...

output:

100 51
51 35
35 50
79 44
44 28
28 2
2 11
80 21
21 97
41 93
93 76
76 8
8 19
19 4
64 14
14 5
88 66
66 6
69 77
77 83
83 75
75 16
59 63
63 13
13 42
42 7
7 25
65 53
53 27
32 99
99 20
20 82
48 98
98 58
58 46
46 24
90 22
22 72
95 67
67 91
17 54
54 94
94 24
29 87
87 23
81 39
39 8
45 76
68 58
74 50
36 40
40 ...

result:

ok correct answer! (200 test cases)

Test #8:

score: 0
Accepted
time: 109ms
memory: 7548kb

input:

8
500
1 88 319 198 384 35 153 99 187 426 495 417 170 360 423 375 127 192 19 280 38 291 295 328 303 464 468 76 147 26 155 171 85 484 281 343 231 366 108 474 225 12 10 322 55 62 73 230 478 436 266 109 177 101 34 337 31 351 17 250 183 218 354 139 86 450 347 28 16 258 150 92 293 119 125 227 210 259 345 ...

output:

438 248
248 165
165 58
58 80
488 244
244 240
407 321
321 3
3 290
87 148
148 4
486 374
374 467
413 487
487 6
6 300
414 391
391 84
84 7
286 425
425 135
437 310
310 48
48 61
230 322
322 10
10 12
409 348
348 9
9 166
266 436
436 109
109 177
177 34
34 139
103 318
318 69
69 18
358 33
33 336
443 496
496 379...

result:

ok correct answer! (8 test cases)

Test #9:

score: -100
Wrong Answer
time: 88ms
memory: 7644kb

input:

2
1000
1 590 961 581 207 169 733 887 222 523 203 721 291 165 242 858 912 646 386 491 278 860 701 572 993 418 824 139 344 253 71 108 478 718 712 145 437 212 751 368 804 667 807 725 760 689 958 70 962 528 945 438 177 237 444 516 127 495 633 761 765 119 826 28 74 504 617 256 711 907 540 539 241 604 732...

output:

904 113
113 526
983 2
2 932
668 316
316 281
281 86
802 184
184 4
599 563
563 372
372 267
347 7
7 12
769 213
213 25
808 9
9 399
896 876
876 10
10 787
522 11
11 124
762 816
816 211
211 379
699 821
821 14
14 246
831 879
879 289
289 56
56 137
433 794
794 421
421 188
224 77
77 98
98 26
26 76
947 143
143 ...

result:

wrong answer ord[1] didn't pass the test (test case 1)
English 繁體中文 简体中文

服务器时间: 2024-12-05 01:14:52 | 开源项目