QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#687709#6469. Harry Potter and The Vector SpellLaVuna47#WA 17ms4784kbC++201.8kb2024-10-29 20:37:542024-10-29 20:37:55

Judging History

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

  • [2024-10-29 20:37:55]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:4784kb
  • [2024-10-29 20:37:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;

#ifdef ONPC
mt19937 rnd(228);
#endif


struct DSU
{
	vector<int> p;
	vector<int> S;

	DSU(int n)
	{
		p = vector<int>(n);
		iota(all(p),0);
		S = vector<int>(n, 1);
	}
	
	int find(int v)
	{
		if(v==p[v])
			return v;
		return p[v] = find(p[v]);
	}
	int get_sz(int v)
	{
		v = find(v);
		return S[v];
	}
	void unite(int a, int b)
	{
		a = find(a);
		b = find(b);
		if(a != b)
		{
			S[b] += S[a];
			p[a] = b;
			S[a] = 0;
		}
	}
};

int solve()
{
	int m, n;
	if (!(cin >> m >> n))
		return 1;
	
	vector<pii> ps(n, {-1, -1});
	// m - len of vector
	FOR(i,0,m)
	{
		int k;
		cin >> k;
		
		FOR(_,0,k)
		{
			int el;
			cin >> el;
			--el;
			if(ps[el].x == -1)
				ps[el].x = i;
			else
				ps[el].y = i;
		}
	}

	int rank = 0;
	auto dsu = DSU(m);
	for(auto [x, y]: ps)
	{
		assert(!(x == -1 || y == -1));
		if(dsu.find(x) != dsu.find(y))
		{
			dsu.unite(x, y);
			rank = max(rank, dsu.get_sz(x)-1);
		}
	}
	cout << rank << '\n';
	return 0;	
}

int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int TET = 1e9;
	//cin >> TET;
	for (int i = 1; i <= TET; i++)
	{
		if (solve())
			break;
			
		#ifdef ONPC
			cerr << "_________________________________\n";
		#endif
	}
	#ifdef ONPC
		cerr << "\nfinished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n";
	#endif
	return 0;
}

详细

Test #1:

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

input:

3 3
2 1 3
2 1 2
2 2 3

output:

2

result:

ok single line: '2'

Test #2:

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

input:

93 92
1 49
3 14 37 65
2 78 16
1 6
1 35
3 52 69 28
2 40 38
5 58 91 80 41 19
1 68
1 13
1 52
2 45 50
1 89
4 29 62 2 15
2 73 85
3 74 88 3
1 21
2 7 12
1 51
1 7
1 24
1 9
2 30 59
2 54 79
2 47 25
2 75 63
2 8 20
1 87
3 72 57 83
3 20 81 5
2 5 77
1 92
2 67 45
2 46 15
2 27 63
5 51 12 42 81 37
3 72 56 84
2 2 68
...

output:

92

result:

ok single line: '92'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

838 837
1 214
3 386 757 400
3 239 578 785
2 792 833
2 384 610
2 670 507
1 499
3 812 270 704
4 225 392 529 350
2 719 227
3 173 714 352
5 558 110 290 645 746
4 365 333 155 660
2 241 776
4 773 451 687 811
2 491 120
2 783 626
2 358 191
1 127
3 728 259 323
2 559 769
1 833
1 544
1 166
2 318 59
3 151 824 3...

output:

837

result:

ok single line: '837'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

994 993
19 746 22 109 352 76 609 144 18 697 141 224 547 801 761 687 528 559 829 415
3 753 882 336
1 153
1 36
1 287
1 328
1 467
2 429 237
1 77
1 342
1 307
2 106 279
1 19
1 770
9 623 293 368 571 644 745 394 457 89
5 77 604 350 850 839
1 505
1 102
3 285 97 515
1 877
1 6
1 523
1 777
1 868
7 38 546 936 4...

output:

993

result:

ok single line: '993'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

268 267
8 96 51 230 246 240 127 140 1
5 224 101 106 231 136
4 159 187 150 51
5 21 98 217 214 84
1 196
2 21 75
1 33
1 54
1 250
1 218
1 108
1 161
3 100 128 97
1 78
4 267 8 49 148
2 266 173
1 179
1 170
1 3
1 20
1 219
1 181
2 86 31
2 137 50
1 27
1 244
1 168
1 166
2 182 20
4 131 162 260 121
4 184 138 96 ...

output:

267

result:

ok single line: '267'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

626 625
181 507 560 294 589 492 5 537 511 553 75 16 287 392 493 79 515 306 484 563 98 393 377 557 205 504 341 352 231 66 204 81 69 353 40 80 374 252 78 106 21 581 343 412 128 278 27 595 308 437 386 11 261 337 293 358 213 324 387 624 428 229 369 299 607 339 372 483 618 211 303 541 260 24 70 115 620 6...

output:

625

result:

ok single line: '625'

Test #7:

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

input:

2833 2832
332 1623 742 606 1166 240 2106 169 1141 2391 655 1624 949 2113 350 1376 2096 764 733 1737 2067 1629 1942 2807 920 1481 1362 373 434 1397 2223 1107 2157 1235 873 1285 1204 2725 1447 2713 513 147 1434 1086 1311 1480 1931 621 2340 913 1675 2128 975 1366 347 1577 6 2083 993 1863 667 1279 1722 ...

output:

2832

result:

ok single line: '2832'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

4339 4338
297 2260 3611 618 1116 204 3295 1579 3762 2599 673 400 2182 2192 876 3056 3793 3754 2814 2482 1640 4218 3378 1672 1130 670 2856 4125 3087 1562 1175 3985 983 4292 4190 2830 3778 1648 3979 1443 2586 1635 4236 4290 610 2034 1528 144 3281 2826 45 2221 2805 1468 1964 47 586 373 1475 3824 1619 3...

output:

4338

result:

ok single line: '4338'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

4998 4997
1 3146
2 3906 4083
2 1860 851
1 1748
2 3394 3741
2 4349 3066
1 2322
1 3934
1 3422
2 2904 1029
2 3362 1470
1 3606
2 689 2655
2 1730 2296
2 1817 495
2 4508 3044
3 526 3974 1218
1 3096
1 2112
1 1029
1 4052
2 1555 139
1 1998
1 1103
1 4122
1 4168
1 3070
1 3744
3 1253 4918 4139
2 4483 2764
1 194...

output:

4997

result:

ok single line: '4997'

Test #10:

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

input:

7970 7969
179 141 6744 6542 6875 4535 1817 2763 6800 7520 4874 404 5565 3172 4914 94 1652 7647 7350 3089 4469 6602 745 3277 2978 3269 7821 2153 2847 274 3261 6097 3017 844 3931 5474 5361 4447 176 6972 331 4517 4215 4652 821 720 4365 7758 12 7922 491 3670 2511 6089 4351 4018 1272 1979 7346 4589 2923 ...

output:

7969

result:

ok single line: '7969'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

7343 7342
307 941 4678 6425 4180 7239 1228 427 438 4110 63 5513 3830 751 6883 1665 4295 788 2931 1853 3000 6132 1586 1488 1739 4494 2357 2195 3546 6961 1150 3680 120 1606 6005 2014 5871 3547 57 779 3887 1834 389 3309 761 1750 224 3030 4744 5443 741 914 659 3186 6193 2585 6038 1246 2244 3936 5743 725...

output:

7342

result:

ok single line: '7342'

Test #12:

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

input:

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

output:

3

result:

ok single line: '3'

Test #13:

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

input:

9587 9586
1 7699
2 5815 7162
2 424 972
1 8886
1 7334
2 3144 7255
2 4620 123
1 8306
1 1444
2 7927 7198
2 5947 8798
1 5066
1 262
2 8578 7711
2 3671 4551
2 5582 8307
2 7054 611
2 1593 2357
1 460
1 4314
2 5894 7828
3 4295 6058 9167
3 2928 8220 3228
2 4226 389
1 1354
2 2965 7006
1 5556
1 1852
2 5204 6217...

output:

9586

result:

ok single line: '9586'

Test #14:

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

input:

7510 7509
1 6247
3 5730 6203 1137
3 656 4782 3874
1 1256
1 7476
3 1332 232 1480
1 7348
1 788
1 5013
1 762
1 7128
2 6143 1712
1 5928
2 6859 221
2 5107 1330
3 284 5129 2198
2 3183 2503
4 2984 558 1708 6156
1 5872
2 533 5213
2 182 5225
2 5701 741
2 5071 4675
3 7069 1464 1650
2 1592 4382
1 7149
2 5139 4...

output:

7509

result:

ok single line: '7509'

Test #15:

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

input:

42120 42119
1 22335
4 22957 26766 18486 18281
1 25854
1 95
2 16012 34089
1 35588
1 5121
6 28095 5203 15501 27417 40407 41212
1 26486
2 27503 8298
3 29243 15917 2668
2 11198 21899
5 13868 5215 32915 15950 1532
2 11224 17030
1 29364
1 4912
2 1885 23772
2 6772 10543
2 5933 25243
2 24549 27121
2 1400 20...

output:

42119

result:

ok single line: '42119'

Test #16:

score: 0
Accepted
time: 3ms
memory: 3632kb

input:

17899 17898
417 9634 10218 17823 11516 1217 7262 14641 7130 5637 15080 13743 4457 6134 9305 1423 16503 15864 15098 1850 13512 17668 11796 3341 4218 1924 4169 880 11024 14607 4852 7929 6455 3922 15516 8456 12240 12747 10972 10966 5674 1352 2497 12468 17366 6625 11960 15195 17709 13963 3607 415 4578 1...

output:

17898

result:

ok single line: '17898'

Test #17:

score: 0
Accepted
time: 9ms
memory: 3984kb

input:

51035 51034
33 32218 34317 35882 6301 46366 47476 30286 24415 18911 38902 46203 39054 29708 8359 17963 9400 26209 40542 21457 9298 21860 15839 5637 25043 48607 42605 9579 49853 4470 36438 35506 34257 41985
2 48781 48780
3 29738 35968 35593
2 8439 3148
1 39380
2 30706 6641
1 12810
1 16167
1 43904
1 3...

output:

51034

result:

ok single line: '51034'

Test #18:

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

input:

27181 27180
163 6089 1555 12762 12576 24944 23562 14781 17434 21846 9099 18814 5537 12478 11830 19407 409 24817 13648 9728 24151 11448 12711 769 6972 4844 9829 10257 11396 14225 4483 1870 25923 17080 4044 5210 10578 20498 20459 18698 13627 22058 21856 234 17459 17466 23320 24760 24017 18314 22483 16...

output:

27180

result:

ok single line: '27180'

Test #19:

score: 0
Accepted
time: 3ms
memory: 3928kb

input:

45544 45543
1 2416
2 19562 4955
4 8603 6271 15156 40076
2 21733 13938
3 40213 6130 35092
2 38538 17900
3 12411 44567 36242
1 3422
1 19530
4 39302 44412 30975 39419
1 14391
2 44077 29365
2 42839 35935
2 24492 27921
2 31077 22225
1 31878
1 35098
2 41412 33350
2 4601 45342
4 29563 44163 12245 16627
2 1...

output:

45543

result:

ok single line: '45543'

Test #20:

score: 0
Accepted
time: 8ms
memory: 3880kb

input:

50563 50562
417 11644 388 3658 6036 46824 42539 10701 37994 19428 18635 28222 40025 42247 4677 41111 36417 22487 932 39478 9510 2804 30444 37580 28954 47958 20473 8712 25257 27276 15320 42176 38114 23030 27232 42047 2040 14810 17390 37275 2914 14384 44772 49238 15156 42673 15555 46651 42281 24916 25...

output:

50562

result:

ok single line: '50562'

Test #21:

score: 0
Accepted
time: 16ms
memory: 4632kb

input:

94794 94793
680 36480 47350 37214 39404 22280 9080 57158 89690 90289 28491 59303 19184 56413 65216 35696 63076 85422 28452 114 84470 79694 7083 65794 33803 80830 76036 3341 24321 15780 52134 11875 78200 3782 48427 89404 84051 47939 66827 79301 76024 79658 2358 9862 89138 63959 23573 85248 8827 63969...

output:

94793

result:

ok single line: '94793'

Test #22:

score: 0
Accepted
time: 16ms
memory: 4784kb

input:

96047 96046
1 14111
3 24941 35985 84071
2 40759 32722
1 23360
4 49364 88265 93042 76183
2 46931 22643
2 70816 74680
3 51609 90971 87746
1 20950
3 45517 40647 29069
1 79880
4 45835 86650 41883 94896
5 48178 21313 14788 44382 27571
1 1709
2 93257 2793
4 35967 18166 24220 37610
2 75869 81257
2 67464 72...

output:

96046

result:

ok single line: '96046'

Test #23:

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

input:

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

output:

7

result:

ok single line: '7'

Test #24:

score: 0
Accepted
time: 13ms
memory: 4460kb

input:

82764 82763
1 17011
3 79926 29762 55974
2 67069 79765
2 18101 63553
3 21707 73335 10561
1 66744
2 74350 24814
2 31581 51501
2 62947 66402
1 69879
2 32246 20161
2 56139 40227
2 28750 53758
2 24533 19810
5 17490 1788 63191 13348 43922
3 17951 24093 42911
2 1920 75215
4 31753 48786 55523 5562
2 43438 1...

output:

82763

result:

ok single line: '82763'

Test #25:

score: 0
Accepted
time: 13ms
memory: 4600kb

input:

99892 99891
637 75130 43738 62977 21748 10059 67687 40790 37333 78688 99250 25357 35743 76903 8113 28490 30122 86953 14076 58739 22434 4487 6730 4561 63571 47102 25208 56685 67546 64197 76772 39877 24642 39463 55774 79408 29324 7403 93069 91890 71989 98 72789 86197 28512 32789 28143 20255 83491 6118...

output:

99891

result:

ok single line: '99891'

Test #26:

score: 0
Accepted
time: 17ms
memory: 4636kb

input:

99632 99631
494 60417 36862 62558 64885 12736 74011 79944 68219 84968 69314 62716 63674 27008 72210 43898 37520 65042 72065 30362 58981 88111 73428 77803 71833 33524 34634 43401 50602 47989 96139 47617 58811 69435 85106 30995 66410 7554 64997 82308 48985 45990 3781 7153 7469 26949 58035 23956 57311 ...

output:

99631

result:

ok single line: '99631'

Test #27:

score: 0
Accepted
time: 16ms
memory: 4628kb

input:

99809 99808
1 4279
1 76039
2 81884 81093
1 39571
2 52590 19299
3 83432 19379 83817
1 71043
2 27962 36680
1 53663
1 61885
1 17912
1 68526
1 46122
3 43972 74288 9688
2 94854 34593
2 23027 68226
1 43730
1 25269
2 7860 15170
2 2440 4719
1 90047
1 26885
1 37162
2 62980 4882
4 67801 26903 62858 38101
1 12...

output:

99808

result:

ok single line: '99808'

Test #28:

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

input:

10 3
0
1 1
2 2 3
0
1 3
0
0
1 1
0
1 2

output:

2

result:

wrong answer 1st lines differ - expected: '3', found: '2'