QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#144375#6503. DFS Order 3qzhwlzyWA 113ms7648kbC++141.3kb2023-08-21 16:27:352023-08-21 16:27:39

Judging History

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

  • [2023-08-21 16:27:39]
  • 评测
  • 测评结果：WA
  • 用时：113ms
  • 内存：7648kb
查看
  • [2023-08-21 16:27:35]
  • 提交

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++) if(a[i][a[i][n+1]]==top&&!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: 1ms
memory: 3728kb

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: 107ms
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
4 1
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
5 9
9 1
10 9
4 2
2 10
9 6
6 1
3 8
8 7
7 5
10 6
7 6
2 10
10 3
3 6
8 9
9 1
1 5
5 7
7 4
3 7
7 9
9 8
8 3
2 6
6 10
10 1
4 8
5 10
8 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: 85ms
memory: 5996kb

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
88 73
73 8
31 73
5 100
100 3
3 68
68 40
40 91
91 57
73 49
49 67
67 4
4 19
54 32
32 53
53 4
49 90
90 18
18 48
18 3
76 98
98 24
24 80
80 55
80 22
22 26
26 78
27 97
97 56
56 87
56 33
33 9
9 10
10 43
43 84
84 26
26 68
96 72
72 93
93 62
62 40
75 94
94 63
94 47
47 79
...

result:

ok correct answer! (200 test cases)

Test #4:

score: 0
Accepted
time: 89ms
memory: 5976kb

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
157 25
25 82
289 416
416 227
82 497
497 463
227 408
408 399
399 144
497 324
324 483
496 136
136 414
414 48
48 92
324 2...

result:

ok correct answer! (8 test cases)

Test #5:

score: 0
Accepted
time: 88ms
memory: 7648kb

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: -100
Wrong Answer
time: 113ms
memory: 3752kb

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
5 9
9 8
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
6 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:

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

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