QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344804#6503. DFS Order 3tzxydbyWA 113ms11816kbC++201.4kb2024-03-05 13:10:492024-03-05 13:10:50

Judging History

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

  • [2024-03-05 13:10:50]
  • 评测
  • 测评结果：WA
  • 用时：113ms
  • 内存：11816kb
查看
  • [2024-03-05 13:10:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N][N],p[N][N],ps[N],f[N],c;
int fa(int x){return x==f[x]?x:f[x]=fa(f[x]);}
set<pair<int,int>>s;
vector<int>st;
vector<pair<int,int>>ans;
void add(int x,int y)
{
	if(x>y) swap(x,y);
	if(s.find(make_pair(x,y))!=s.end()) return;
	s.insert(make_pair(x,y));
	c++;
	f[fa(x)]=fa(y);
	for(int i=1;i<=n;i++)
	{
		int px=p[i][x],py=p[i][y];
		if(abs(px-py)==1) continue;
		if(px>py) swap(px,py);
		add(a[i][px],a[i][px+1]);
	}
}
void cal(int x)
{
	while(ps[x]<=n&&fa(x)==fa(a[x][ps[x]]))
		ps[x]++;
}
void sol()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	if(n==1) return;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			p[i][a[i][j]]=j;
	for(int i=1;i<=n;i++)
		f[i]=i,ps[i]=1;
	s.clear();
	c=0;
	for(int i=1;i<=n;i++)
		add(a[i][1],a[i][2]);
	while(c!=n-1)
	{
		int ls=1,t=0;
		while(1)
		{
			cal(ls);
			int nx=a[ls][ps[ls]];
			cal(nx);
			if(a[nx][ps[nx]]==ls)
			{
				add(ls,nx);
				break;
			}
			ls=nx;
			t++;
			if(t>n)
			{
				for(int i=1;i<=n;i++)
				{
					for(int j=1;j<=n;j++)
						printf("%d ",a[i][j]);
					puts("");
				}
				exit(0);
			}
		}
	}
	for(auto [i,j]:s)
		ans.emplace_back(i,j);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
		sol();
	for(auto [i,j]:ans)
		printf("%d %d\n",i,j);
	return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

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

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:

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

result:

ok correct answer! (4 test cases)

Test #2:

score: 0
Accepted
time: 113ms
memory: 7364kb

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:

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

result:

ok correct answer! (20000 test cases)

Test #3:

score: 0
Accepted
time: 99ms
memory: 8484kb

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:

1 29
1 45
1 51
2 5
3 18
3 68
3 100
4 19
4 53
4 67
5 41
5 95
5 100
6 16
6 23
7 34
8 73
9 10
9 33
10 43
11 44
12 47
12 81
12 91
13 65
13 74
14 60
14 69
15 20
15 66
16 81
17 47
17 50
18 48
18 90
20 21
20 45
21 71
22 26
22 80
23 37
24 80
24 98
25 99
26 68
26 78
26 84
27 97
28 86
29 77
29 82
30 95
31 73
...

result:

ok correct answer! (200 test cases)

Test #4:

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

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:

1 164
2 110
2 268
2 337
3 69
3 495
4 304
5 124
5 208
6 8
6 100
6 205
7 308
7 396
8 368
8 373
9 77
9 240
10 135
11 46
11 73
11 117
11 186
11 203
11 312
12 27
12 219
13 404
13 425
13 426
14 23
14 374
15 156
15 234
15 494
16 282
16 389
17 238
18 346
19 295
20 176
21 38
21 303
21 306
22 101
22 155
23 74...

result:

ok correct answer! (8 test cases)

Test #5:

score: 0
Accepted
time: 106ms
memory: 11816kb

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:

1 586
2 609
2 655
2 695
3 552
3 761
4 532
5 677
5 730
6 105
6 720
6 818
7 258
7 451
8 203
8 414
8 626
9 152
9 860
9 878
10 201
11 757
11 807
12 562
12 759
13 160
13 212
13 757
14 663
14 826
15 143
15 406
16 595
17 889
18 572
18 673
19 502
19 842
20 97
20 323
20 858
21 409
21 666
22 465
22 751
23 214...

result:

ok correct answer! (2 test cases)

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 5892kb

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:

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

result:

wrong answer your output is not a tree (test case 1)
English 繁體中文 简体中文

伺服器時間: 2024-12-02 22:26:52 | 開源專案