QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#677258#7738. Equivalent RewritingrealisationWA 616ms147420kbC++201.7kb2024-10-26 10:50:102024-10-26 10:50:13

Judging History

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

  • [2024-10-26 10:50:13]
  • 评测
  • 测评结果:WA
  • 用时:616ms
  • 内存:147420kb
  • [2024-10-26 10:50:10]
  • 提交

answer

#include<bits/stdc++.h>

#define int long long 
#define endl '\n'
using namespace std ;

const int N = 1e5 + 10;

vector<int> d[N], g[N];
map<int,int> mp[N];
int cnt[N], a[N];

void solve() {

	int n, m;
	cin>>n>>m;

	for(int i=1;i<=n;i++) mp[i].clear(), g[i].clear(), cnt[i] = 0;
	for(int i=1;i<=m;i++) a[i] = 0, d[i].clear();
	for(int i=1;i<=n;i++) {
		int x;
		cin>>x;
		for(int j=1;j<=x;j++) {
			int y;
			cin>>y;
			a[y] = i;
			d[y].push_back(i);
		}
	}

	for(int i=1;i<=m;i++) {
		int v = a[i];
		for(int u : d[i]) {
			if(mp[u][v]||mp[v][u]||u==v) continue;
			mp[u][v] = mp[v][u] = 1;
			g[u].push_back(v);
			cnt[v]++;
		}
	}

	queue<int> q;
	for(int i=n;i>=1;i--) {
		if(!cnt[i]) {
			q.push(i);
		}
	}

	int cur = 0;
	int ok = 0;
	vector<int> ans;	
	while(!q.empty()) {
		int u = q.front();
		ans.push_back(u);
		cur++;
		q.pop();
		vector<int> e;
		for(int v : g[u]) {
			cnt[v]--;
			if(!cnt[v]) e.push_back(v);
		}
		int ff = 0;
		for(int x : e) {
			if(cur+1!=x) {
				ff = x;
				break;
			}
		}
		if(ff) {
			ok = 1;
			cur++;
			q.push(ff);
			for(int x : e) {
				if(ff==x) continue;
				q.push(x);
				cur++;
			}
		}
		else {
			for(int x : e) {
				cur++;
				q.push(x);
			}
		}
	}

	int len = ans.size(), f = 0;
	for(int i=0;i<len;i++) {
		if(ans[i]!=i+1) {
			f = 1;
		}
	}
	if(!f&&!ok) {
		cout<<"No"<<endl;
		return ;
	}

	cout<<"Yes"<<endl;
	for(int i=0;i<len-1;i++) cout<<ans[i]<<" ";
	cout<<ans.back()<<endl;

}

signed main() {

	ios::sync_with_stdio(0) ;
	cout.tie(0) ;
	cin.tie(0) ;
	int t = 1;
	cin >> t;
	while(t --){
		solve() ;
	}
	return 0 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9688kb

input:

3
3 6
3 3 1 5
2 5 3
2 2 6
2 3
3 1 3 2
2 3 1
1 3
2 2 1

output:

Yes
3 1 2
No
No

result:

ok OK. (3 test cases)

Test #2:

score: 0
Accepted
time: 2ms
memory: 9724kb

input:

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

output:

Yes
8 7 6 5 4 3 2 1 9 10

result:

ok OK. (1 test case)

Test #3:

score: 0
Accepted
time: 0ms
memory: 9896kb

input:

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

output:

Yes
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 19 20

result:

ok OK. (1 test case)

Test #4:

score: 0
Accepted
time: 2ms
memory: 9848kb

input:

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

output:

Yes
36 35 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 34 39 38 37 40

result:

ok OK. (1 test case)

Test #5:

score: 0
Accepted
time: 2ms
memory: 11820kb

input:

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

output:

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

result:

ok OK. (1 test case)

Test #6:

score: 0
Accepted
time: 0ms
memory: 11132kb

input:

1
5000 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

output:

Yes
4999 4998 4997 4996 4995 4994 4993 4992 4991 4990 4989 4988 4987 4986 4985 4984 4983 4982 4981 4980 4979 4978 4977 4976 4975 4974 4973 4972 4971 4970 4969 4968 4967 4966 4965 4964 4963 4962 4961 4960 4959 4958 4957 4956 4955 4954 4953 4952 4951 4950 4949 4948 4947 4946 4945 4944 4943 4942 4941 4...

result:

ok OK. (1 test case)

Test #7:

score: 0
Accepted
time: 34ms
memory: 19752kb

input:

1
5000 200
2 121 161
35 27 5 1 189 173 2 37 107 140 172 108 53 163 19 127 102 174 71 178 42 72 74 167 118 120 175 28 75 128 106 190 112 86 171 13
109 110 109 183 17 77 159 188 157 56 14 104 55 179 121 171 64 123 196 140 38 29 134 130 163 108 187 42 68 26 156 138 80 143 182 4 174 67 63 76 79 69 142 3...

output:

Yes
4995 4991 4990 4989 4988 4987 4986 4985 4984 4983 4982 4981 4980 4979 4978 4977 4976 4975 4974 4973 4972 4971 4970 4969 4968 4967 4966 4965 4964 4963 4962 4961 4960 4959 4958 4957 4956 4955 4954 4953 4952 4951 4950 4949 4948 4947 4946 4945 4944 4943 4942 4941 4940 4939 4938 4937 4936 4935 4934 4...

result:

ok OK. (1 test case)

Test #8:

score: 0
Accepted
time: 609ms
memory: 146956kb

input:

1
5000 1000
146 147 426 393 758 104 385 277 218 753 477 377 54 465 635 918 97 453 576 270 57 189 230 227 332 345 358 14 178 969 817 840 620 828 837 94 922 844 789 106 250 952 745 212 693 296 677 368 625 150 103 55 266 756 525 60 91 683 364 852 877 792 312 315 997 27 50 866 759 327 557 56 49 947 644 ...

output:

Yes
4955 4954 4943 4940 4939 4914 4900 4898 4887 4854 4853 4842 4836 4826 4815 4804 4803 4797 4793 4788 4780 4777 4773 4768 4766 4755 4746 4741 4737 4729 4718 4709 4705 4701 4700 4698 4694 4691 4686 4681 4679 4678 4677 4676 4674 4673 4672 4667 4661 4657 4655 4650 4648 4647 4646 4645 4644 4635 4634 4...

result:

ok OK. (1 test case)

Test #9:

score: 0
Accepted
time: 616ms
memory: 147420kb

input:

1
4999 1000
799 991 88 253 814 577 620 74 338 485 560 435 835 130 279 536 637 188 612 876 634 950 755 534 727 272 657 357 810 113 800 41 439 125 763 311 724 623 976 525 725 869 209 975 888 683 428 4 91 448 936 885 140 233 967 556 369 522 263 483 784 96 808 70 42 391 109 333 778 422 121 862 430 746 6...

output:

Yes
4943 4939 4936 4925 4923 4911 4900 4897 4894 4892 4882 4876 4872 4860 4853 4839 4830 4820 4817 4810 4795 4787 4784 4766 4761 4755 4750 4747 4746 4741 4738 4737 4731 4729 4719 4716 4714 4711 4709 4708 4702 4695 4693 4692 4689 4680 4675 4670 4669 4666 4661 4660 4657 4654 4648 4646 4645 4643 4642 4...

result:

ok OK. (1 test case)

Test #10:

score: 0
Accepted
time: 427ms
memory: 102912kb

input:

1
5000 5000
2081 3619 2779 2556 4025 163 2942 2539 4075 189 2823 2189 3571 1168 1474 3383 649 1432 2052 1218 645 1053 1833 2651 3651 1611 1512 1267 3727 4182 2237 4827 3905 3335 3268 1627 2212 3697 2241 884 4015 4902 1504 2223 484 3001 2908 4619 4321 2875 4501 87 2442 3850 2760 834 3985 1807 1880 26...

output:

Yes
4981 4807 4801 4763 4754 4665 4660 4649 4643 4640 4637 4629 4615 4612 4605 4587 4579 4572 4571 4564 4562 4559 4530 4520 4502 4480 4471 4462 4452 4442 4441 4437 4415 4405 4386 4384 4383 4381 4378 4352 4343 4338 4334 4318 4305 4297 4285 4263 4260 4259 4250 4241 4239 4236 4235 4227 4223 4222 4221 4...

result:

ok OK. (1 test case)

Test #11:

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

input:

1
1000 5000
2728 456 1809 201 2171 4389 1597 1911 2218 3081 3818 486 3732 263 2483 2923 527 867 782 3405 3803 4039 838 3743 3589 2153 2818 2946 997 11 899 2656 2024 4474 4802 2978 2070 3056 1919 2475 2205 2563 4339 3179 2508 195 3943 3710 4441 3440 3923 4842 3916 4481 912 3076 4866 710 254 4324 1546...

output:

Yes
876 858 848 846 815 785 780 705 677 667 650 625 622 621 608 586 580 575 563 541 529 513 512 507 504 486 478 473 472 471 462 457 446 427 426 394 377 376 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 ...

result:

ok OK. (1 test case)

Test #12:

score: 0
Accepted
time: 5ms
memory: 11044kb

input:

1
10 5000
4665 1548 2583 767 790 1820 825 4120 4957 4179 3273 2273 4509 457 3495 667 206 1152 4353 1992 4211 315 4334 905 4043 2826 1094 1708 4132 1046 3359 137 3773 4602 4557 83 605 4257 3514 4430 4968 2253 3041 786 2356 320 1504 1734 4095 1738 2512 3667 140 1487 594 276 3290 4273 4321 87 3343 4451...

output:

Yes
4 3 2 1 5 6 7 8 9 10

result:

ok OK. (1 test case)

Test #13:

score: 0
Accepted
time: 410ms
memory: 101900kb

input:

1
4999 4999
1640 2673 1066 1994 4702 3817 839 2285 742 4086 1810 4349 4925 4974 4073 3186 3272 4258 893 3357 942 1513 1881 1371 2140 1512 4472 524 2119 3396 1236 4311 4605 1337 910 586 944 1016 4661 1041 2765 481 4021 4994 712 1233 3011 2070 123 356 2703 3891 2559 1158 640 1127 1488 2836 1912 3975 4...

output:

Yes
4896 4869 4863 4860 4804 4785 4784 4762 4731 4729 4711 4709 4697 4691 4684 4672 4661 4655 4630 4616 4599 4597 4592 4587 4576 4542 4539 4535 4530 4528 4526 4524 4502 4499 4487 4485 4471 4465 4419 4406 4397 4390 4383 4362 4360 4358 4353 4350 4347 4341 4332 4313 4311 4278 4277 4269 4265 4261 4256 4...

result:

ok OK. (1 test case)

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 10136kb

input:

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

output:

Yes
1 2 3 4 5 6 7 8 9 10

result:

wrong answer two transactions are same. (test case 1)