QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485576#4938. Writing TasksPetroTarnavskyiWA 245ms63680kbC++143.1kb2024-07-20 20:12:282024-07-20 20:12:28

Judging History

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

  • [2024-07-20 20:12:28]
  • 评测
  • 测评结果:WA
  • 用时:245ms
  • 内存:63680kb
  • [2024-07-20 20:12:28]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#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--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

mt19937 rng;

struct Graph
{
	int szL, szR;
	
	vector<VI> g;
	VI mateForR, mateForL, usedL;
	
	void init(int L, int R)
	{
		szL = L, szR = R;
		g.resize(szL);
		mateForL.resize(szL);
		usedL.resize(szL);
		
		mateForR.resize(szR);
	}
	
	void addEdge(int from, int to)
	{
		assert(0 <= from && from < szL);
		assert(0 <= to && to < szR);
		
		g[from].PB(to);
	}
	
	int iter;
	
	bool kuhn(int v)
	{
		if (usedL[v] == iter) return false;
		usedL[v] = iter;
		shuffle(ALL(g[v]), rng);
		for (int to : g[v])
		{
			if (mateForR[to] == -1)
			{
				mateForR[to] = v;
				mateForL[v] = to;
				return true;
			}
		}
		for (int to : g[v])
		{
			if (kuhn(mateForR[to]))
			{
				mateForR[to] = v;
				mateForL[v] = to;
				return true;
			}
		}
		return false;
	}
	
	int doKuhn()
	{
		fill(ALL(mateForR), -1);
		fill(ALL(mateForL), -1);
		fill(ALL(usedL), -1);
		
		int res = 0;
		iter = 0;
		while (true)
		{
			iter++;
			bool ok = false;
			FOR (v, 0, szL)
			{
				if (mateForL[v] == -1)
				{
					if (kuhn(v))
					{
						ok = true;
						res++;
					}
				}
			}
			if (!ok)
				break;
		}
		return res;
	}
};

const int N = 200'447;

VI g[N];

int used[N];
bool ok = 1;

int col[N];
void dfs(int v)
{
	used[v] = 1;
	for(int to : g[v])
	{
		if(used[to])
		{
			if(col[to] == col[v])
				ok = 0;
		}
		else
		{
			col[to] = col[v] ^ 1;
			dfs(to);
		}
	}
}



int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, c, t;
	cin >> a >> c >> t;
	
	FOR (i, 0, a)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[i].PB(a + x - 1);
		}
	}
	FOR (i, 0, a)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[i].PB(a + c + x - 1);
		}
	}
	
	FOR (i, 0, c)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[a + i].PB(a + c + x - 1);
		}
	}
	
	map<PII, VI> m;
	
	int cnt = 0;
	
	FOR (i, 0, a)
	{
		set<int> susids;
		for (auto to : g[i])
			susids.insert(to);
		for (auto u : g[i])
		{
			for (auto v : g[u])
			{
				if (!susids.count(v))
					continue;
				m[{i, u}].PB(cnt);
				m[{i, v}].PB(cnt);
				m[{u, v}].PB(cnt);
				cnt++;
			}
		}
	}
	FOR(i, 0, a + c + t)
		g[i].clear();
	
	Graph G;
	G.init(cnt, cnt);
	for (auto [p, v] : m)
	{
		assert(SZ(v) <= 2);
		if (SZ(v) == 2)
		{
			G.addEdge(v[0], v[1]);
			G.addEdge(v[1], v[0]);
			
			g[v[0]].PB(v[1]);
			g[v[1]].PB(v[0]);
		}
	}
	int ans = cnt - G.doKuhn() / 2;
	FOR(i, 0, cnt)
	{
		if(used[i])
			continue;
		dfs(i);
	}
	if(!ok)
		ans--;
	
	
	cout << ans << '\n';
	
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3 2
2 1 2
2 2 3
1 1
1 1
1 1
1 1
1 2

output:

2

result:

ok single line: '2'

Test #2:

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

input:

2 2 2
0
1 2
0
2 1 2
2 1 2
0

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 186ms
memory: 50408kb

input:

40623 39265 42226
2 14643 37432
2 29610 20181
2 6441 7614
2 17559 3238
2 39001 17644
2 6431 37097
2 6347 12246
2 1130 1688
2 38583 9078
2 8746 27832
2 13090 39048
2 32647 18777
2 27505 19277
2 31201 25824
2 6133 20344
2 11625 20997
2 18528 35730
0
2 22986 5273
2 10942 38791
2 19025 35679
2 32321 124...

output:

78528

result:

ok single line: '78528'

Test #4:

score: 0
Accepted
time: 182ms
memory: 50388kb

input:

41022 39421 42288
2 26413 2168
2 24182 14199
2 18798 17846
2 3398 19624
2 16796 33998
2 7209 25883
2 26356 13537
2 56 30294
2 34909 20218
2 29727 22116
2 16349 1704
2 9254 18036
2 16197 16096
2 21562 31470
2 14773 10518
2 38025 12573
2 15509 32276
2 9613 12321
2 19146 11395
2 7186 36431
0
2 10098 22...

output:

78840

result:

ok single line: '78840'

Test #5:

score: 0
Accepted
time: 217ms
memory: 55096kb

input:

49395 43808 45888
2 13031 11323
2 41375 4393
2 32137 17908
2 29053 42691
0
2 38335 30970
2 38318 43773
2 22999 22444
0
2 39248 30837
0
2 29807 2360
2 29363 3536
2 8515 41137
2 7890 31441
0
2 31070 6987
2 24295 15517
2 14204 13069
2 32996 40146
2 38164 1478
2 40032 19143
0
2 18430 24119
2 37845 33290...

output:

87616

result:

ok single line: '87616'

Test #6:

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

input:

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

output:

5

result:

ok single line: '5'

Test #7:

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

input:

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

output:

15

result:

ok single line: '15'

Test #8:

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

input:

769 869 792
1 254
2 210 794
1 863
2 40 403
2 279 773
2 54 328
2 196 473
1 804
1 261
1 174
1 219
1 22
1 429
1 195
2 769 100
1 33
1 457
1 604
2 473 714
2 423 227
2 453 654
1 864
2 220 243
2 520 321
2 421 805
2 721 11
2 216 793
1 360
1 169
2 121 613
2 714 594
1 692
2 642 607
2 538 781
2 800 387
2 494 5...

output:

769

result:

ok single line: '769'

Test #9:

score: 0
Accepted
time: 44ms
memory: 24964kb

input:

46352 41211 38602
2 11300 5679
2 2876 4114
2 28525 6628
1 23785
1 30940
1 26982
1 8056
1 13748
2 25254 21974
1 3446
2 2294 13453
0
1 16724
2 36970 18406
2 7688 17413
1 25901
1 39238
1 16098
1 29911
2 15113 849
1 31293
2 32195 13287
0
1 12670
2 40732 19567
2 24195 23787
1 40913
2 18820 10009
0
0
2 23...

output:

38602

result:

ok single line: '38602'

Test #10:

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

input:

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

output:

3

result:

ok single line: '3'

Test #11:

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

input:

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

output:

16

result:

ok single line: '16'

Test #12:

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

input:

942 753 814
2 429 543
1 228
1 442
0
0
2 215 635
1 199
2 735 727
1 335
2 56 209
2 668 570
2 748 190
2 719 571
0
1 650
1 468
1 646
2 150 547
2 551 53
0
1 203
0
2 544 664
1 100
2 388 321
1 94
1 77
2 535 253
1 306
0
2 753 342
2 690 529
2 204 712
2 621 693
1 253
1 549
2 712 639
2 43 323
2 206 585
2 82 45...

output:

753

result:

ok single line: '753'

Test #13:

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

input:

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

output:

5

result:

ok single line: '5'

Test #14:

score: 0
Accepted
time: 55ms
memory: 25916kb

input:

48398 47836 40164
2 18023 23816
0
0
1 14256
1 47537
2 40419 28208
2 24335 20756
2 11563 31099
2 11298 27901
1 43928
1 4795
2 33599 41395
1 40893
2 24858 20153
1 16524
2 73 9844
2 18804 12559
1 47263
1 36093
2 19492 7210
2 10991 38704
2 44074 26169
1 9493
2 23707 40251
1 19203
2 14974 45727
1 15661
2...

output:

40164

result:

ok single line: '40164'

Test #15:

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

input:

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

output:

4

result:

ok single line: '4'

Test #16:

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

input:

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

output:

19

result:

ok single line: '19'

Test #17:

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

input:

858 936 831
1 78
2 132 126
0
2 761 378
1 914
1 36
2 884 480
2 344 531
2 718 395
2 30 270
2 503 495
2 717 520
1 833
2 483 636
1 498
2 181 250
2 538 311
0
2 246 552
1 201
2 598 595
2 672 747
2 823 508
2 429 369
1 705
2 929 659
1 866
2 423 31
2 425 921
2 422 313
2 927 726
1 194
2 553 919
2 733 323
1 12...

output:

831

result:

ok single line: '831'

Test #18:

score: 0
Accepted
time: 50ms
memory: 26576kb

input:

49781 42895 45291
1 29407
1 9103
2 5324 6026
1 31374
2 5841 29212
2 23318 30169
0
2 25579 21864
1 32335
2 23800 806
2 25593 11060
2 15157 69
1 34355
2 2925 14080
2 33167 18126
2 7104 5549
2 40443 5056
2 28415 696
1 4790
1 7018
2 3471 21650
2 2916 40765
1 34240
2 42308 18364
1 38483
0
2 1698 11488
1 ...

output:

42895

result:

ok single line: '42895'

Test #19:

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

input:

2 2 2
1 2
2 2 1
1 1
2 1 2
2 1 2
1 1

output:

2

result:

ok single line: '2'

Test #20:

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

input:

2 2 2
1 2
2 2 1
1 2
2 2 1
2 2 1
1 2

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 74ms
memory: 28736kb

input:

19293 19293 19293
2 15559 6355
2 18678 12383
2 10518 2914
2 9321 5480
2 2515 9636
2 348 6411
2 8068 5686
2 13171 5869
2 3983 3883
2 11207 18235
2 6332 13692
2 9259 8353
2 18013 1039
2 14419 10593
2 14504 3897
2 3936 12241
2 7111 14415
2 9387 11892
2 6697 4039
2 8091 9046
2 4286 14361
2 17222 5305
2 ...

output:

28939

result:

ok single line: '28939'

Test #22:

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

input:

20 20 20
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
0
0
0
0
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
0
0
0
0
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2...

output:

22

result:

ok single line: '22'

Test #23:

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

input:

1000 1000 1000
1 1
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
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
2 20 21
1 22
2 22 23
2 23 24
2 24 25
2 25 26
2 26 27
2 27 28
2 28 29
2 29 30
2 30 31
2 31 32
2 32 33
2 33 34
2 34 35
2 35 36
2 36 37
2 37 38
2 38 ...

output:

1292

result:

ok single line: '1292'

Test #24:

score: 0
Accepted
time: 30ms
memory: 12388kb

input:

42099 49103 43206
2 2436 21573
2 9996 23380
2 18655 46120
2 12927 46150
2 40795 5903
2 21860 35021
2 35508 10085
2 15704 5818
2 4284 22266
2 21850 28412
2 25375 24412
2 5997 38671
2 14067 26688
2 29986 225
2 8819 39574
2 28550 12704
2 6055 4336
2 14012 21939
2 13223 10017
2 36352 23453
2 41234 13597...

output:

6

result:

ok single line: '6'

Test #25:

score: 0
Accepted
time: 98ms
memory: 50596kb

input:

50000 50000 50000
1 1
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
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
2 20 21
2 21 22
2 22 23
2 23 24
2 24 25
2 25 26
2 26 27
2 27 28
2 28 29
2 29 30
2 30 31
2 31 32
2 32 33
2 33 34
2 34 35
2 35 36
2 36 37
2 37 38...

output:

65098

result:

ok single line: '65098'

Test #26:

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

input:

797 781 965
2 542 265
2 613 195
2 483 758
2 387 62
2 9 45
2 146 38
2 305 457
2 374 18
2 776 273
2 475 432
2 691 108
2 264 284
2 70 598
2 741 673
2 393 480
2 250 145
2 740 748
2 35 221
2 442 229
2 204 326
2 304 538
2 721 685
2 58 778
2 51 740
2 750 227
2 25 389
2 142 462
2 557 370
2 30 147
2 28 300
2...

output:

960

result:

ok single line: '960'

Test #27:

score: 0
Accepted
time: 147ms
memory: 44984kb

input:

48703 42977 49346
2 8620 24764
2 14087 32876
0
2 8945 5627
2 41296 34519
0
2 29062 5131
2 816 1371
2 29401 1787
0
2 10358 19458
2 611 26890
2 32600 33419
2 7484 25258
2 18804 27934
2 40145 24038
2 10559 8176
2 17733 7525
2 12422 37383
2 1438 41231
2 40252 30643
0
0
2 6532 38724
2 19246 9753
2 19848 ...

output:

56108

result:

ok single line: '56108'

Test #28:

score: 0
Accepted
time: 4ms
memory: 9940kb

input:

802 787 751
2 138 295
2 572 302
2 575 580
2 556 248
2 642 441
2 638 379
2 650 79
2 397 313
2 464 757
2 753 483
2 461 61
2 506 367
2 582 62
2 350 616
2 19 284
2 196 658
2 483 683
2 588 526
2 106 333
2 478 23
2 640 442
2 781 525
2 362 193
2 323 691
2 648 627
2 784 355
2 399 51
2 662 105
2 107 53
2 417...

output:

928

result:

ok single line: '928'

Test #29:

score: 0
Accepted
time: 153ms
memory: 43276kb

input:

41866 41104 47356
2 14498 27153
2 11889 11501
2 24507 26825
2 9375 38374
2 36646 26596
2 27810 2781
2 18125 31616
2 28814 7751
2 3726 32390
2 24020 9158
2 23175 26847
2 30193 20375
2 33609 14680
2 12657 26318
2 36465 1173
2 40844 30906
0
2 17851 11228
2 15337 33580
0
2 35061 16536
2 1967 3490
2 1256...

output:

54184

result:

ok single line: '54184'

Test #30:

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

input:

849 766 854
1 150
2 721 416
2 716 277
1 336
2 471 535
1 621
2 661 638
2 201 751
0
2 705 67
2 350 24
2 118 131
2 124 704
2 66 511
2 577 200
2 406 733
2 749 312
0
2 114 168
2 472 18
2 83 398
2 261 591
2 627 433
2 60 454
2 371 351
2 70 706
2 143 35
2 477 133
2 365 38
1 126
1 525
2 587 74
0
2 162 225
2 ...

output:

935

result:

ok single line: '935'

Test #31:

score: 0
Accepted
time: 151ms
memory: 42348kb

input:

40473 42204 46693
2 17306 29840
2 21655 27206
2 1577 30755
2 9303 38135
2 13899 38726
2 25718 5486
0
2 13674 32709
2 3258 1310
2 19078 6271
2 32222 38810
2 18668 28018
2 9005 31601
2 31888 40637
2 32991 7539
2 40415 29067
2 33572 39589
2 26823 19361
2 38360 8413
2 4352 12745
2 40742 38924
2 14996 19...

output:

53046

result:

ok single line: '53046'

Test #32:

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

input:

3 3 3
2 3 1
2 2 1
2 3 2
2 1 3
2 2 3
2 1 2
2 2 3
2 1 2
2 1 3

output:

4

result:

ok single line: '4'

Test #33:

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

input:

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

output:

6

result:

ok single line: '6'

Test #34:

score: 0
Accepted
time: 245ms
memory: 63680kb

input:

50000 50000 50000
2 45046 28892
2 26220 33823
2 46837 49104
2 3917 21543
2 22880 20259
2 25075 24819
2 28379 7777
2 801 36871
2 44187 21466
2 8706 16158
2 15338 39721
2 39723 29802
2 34539 5470
2 10200 49750
2 21699 20778
2 6058 31648
2 38204 40071
2 23548 503
2 49337 49734
2 38822 41362
2 47146 283...

output:

75000

result:

ok single line: '75000'

Test #35:

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

input:

1 1 2
0
0
0

output:

0

result:

ok single line: '0'

Test #36:

score: -100
Wrong Answer
time: 157ms
memory: 41604kb

input:

39951 46036 43531
2 35094 23951
2 18866 21023
2 32805 10424
2 35955 45509
2 189 5168
2 34865 13037
2 8649 20563
2 24042 31856
2 25255 38915
2 7464 35453
2 25282 29391
1 20283
0
2 34325 20208
2 4126 28607
2 30645 33252
2 16224 5621
2 785 29439
0
2 4746 31449
2 27519 15163
2 41348 17178
2 42965 18260
...

output:

51959

result:

wrong answer 1st lines differ - expected: '51923', found: '51959'