QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#144786#6503. DFS Order 3qzzyqWA 31ms11548kbC++141.7kb2023-08-21 18:47:082023-08-21 18:47:19

Judging History

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

  • [2023-08-21 18:47:19]
  • 评测
  • 测评结果：WA
  • 用时：31ms
  • 内存：11548kb
查看
  • [2023-08-21 18:47:08]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
inline int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,d[maxn][maxn],p[maxn][maxn];
int fa[maxn],stac[maxn],tot;
inline void dfs(int x) {
	int i;
	if (tot) {
		int id=stac[1];
		for (i=1;i<=tot;i++) if (p[x][stac[i]]<p[x][id]) id=stac[i];
//		gdb(x,id);
//		gdb(p[x][1],p[x][2],p[x][3],p[x][4]);
		fa[x]=id;		
		while (stac[tot]!=id) tot--;
	}
	stac[++tot]=x;
	for (i=2;i<=n;i++) if (!fa[d[x][i]]) dfs(d[x][i]);
}
inline void solve(void) {
	int i,j;
	read(n);
	for (i=1;i<=n;i++) fa[i]=0;
	for (i=1;i<=n;i++) 
		for (j=1;j<=n;j++) 
			read(d[i][j]),p[i][d[i][j]]=j;
	tot=0;fa[1]=n+1;dfs(1);
	for (i=2;i<=n;i++) printf("%d %d\n",i,fa[i]);
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5716kb

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
2 1
3 2
2 1
3 2
4 2
2 1
3 1
4 2
5 3

result:

ok correct answer! (4 test cases)

Test #2:

score: 0
Accepted
time: 31ms
memory: 5768kb

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:

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

result:

ok correct answer! (20000 test cases)

Test #3:

score: 0
Accepted
time: 28ms
memory: 6120kb

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:

2 5
3 68
4 67
5 100
6 16
7 34
8 73
9 10
10 43
11 44
12 47
13 74
14 69
15 20
16 81
17 47
18 3
19 4
20 45
21 20
22 26
23 6
24 80
25 99
26 68
27 97
28 86
29 1
30 95
31 73
32 53
33 9
34 58
35 69
36 44
37 23
38 50
39 92
40 91
41 5
42 52
43 84
44 60
45 1
46 82
47 79
48 18
49 90
50 17
51 1
52 74
53 4
54 32...

result:

ok correct answer! (200 test cases)

Test #4:

score: 0
Accepted
time: 20ms
memory: 9672kb

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:

2 337
3 495
4 304
5 124
6 100
7 396
8 6
9 240
10 135
11 186
12 219
13 425
14 23
15 494
16 282
17 238
18 346
19 295
20 176
21 303
22 155
23 74
24 90
25 82
26 338
27 12
28 415
29 70
30 151
31 147
32 374
33 405
34 238
35 157
36 381
37 455
38 21
39 120
40 338
41 358
42 424
43 372
44 429
45 431
46 11
47 ...

result:

ok correct answer! (8 test cases)

Test #5:

score: 0
Accepted
time: 18ms
memory: 11548kb

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:

2 695
3 552
4 532
5 730
6 105
7 258
8 626
9 878
10 201
11 757
12 562
13 160
14 663
15 143
16 595
17 889
18 572
19 842
20 323
21 409
22 751
23 948
24 310
25 718
26 356
27 263
28 767
29 504
30 359
31 617
32 661
33 287
34 877
35 376
36 682
37 939
38 888
39 555
40 297
41 84
42 314
43 777
44 548
45 145
4...

result:

ok correct answer! (2 test cases)

Test #6:

score: -100
Wrong Answer
time: 25ms
memory: 5692kb

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:

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

result:

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

服务器时间: 2024-12-05 00:51:47 | 开源项目