QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153466#6354. 4nicksmsTL 759ms6792kbC++171.4kb2023-08-30 05:17:192023-08-30 05:17:19

Judging History

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

  • [2023-08-30 05:17:19]
  • 评测
  • 测评结果:TL
  • 用时:759ms
  • 内存:6792kb
  • [2023-08-30 05:17:19]
  • 提交

answer

/**
 *      Author:  Nicholas Winschel
 *      Created: 08.29.2023 16:52:11
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

int main() {
	cin.tie(0)->sync_with_stdio(0); // initialize fast I/O

	int n, m; cin >> n >> m;
	V<pi> edgs; edgs.reserve(m);
	vi cnt(n);
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		u--,v--;
		cnt[u]++, cnt[v]++;
		edgs.emplace_back(u,v);
	}
	vi dec(n); iota(dec.begin(), dec.end(), 0);
	sort(dec.begin(), dec.end(), [&](int x, int y) -> bool {
		return cnt[x] < cnt[y];
	});
	vi enc(n);
	for (int i = 0; i < n; i++) enc[dec[i]]=i;
	V<vi> adj(n);
	for (auto &&p : edgs) {
		p.f = enc[p.f];
		p.s = enc[p.s];
		if (p.f < p.s) swap(p.f, p.s);
		adj[p.f].push_back(p.s);
	}
	V<int> cur(n, -1);
	using bs = bitset<450>;
	ll tot = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < sz(adj[i]); j++) {
			cur[adj[i][j]] = j;
		}
		V<bs> work(sz(cur));
		for (int x : adj[i]) {
			for (int y : adj[x]) {
				if (cur[y] != -1) {
					tot += (work[cur[x]]&work[cur[y]]).count();
					work[cur[x]][cur[y]] = work[cur[y]][cur[x]] = 1;
				}
			}
		}
		for (int j : adj[i]) cur[j] = -1;
	}
	cout << tot << "\n";
	return 0;
}

详细

Test #1:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

50 50
28 35
12 24
31 50
10 24
21 44
5 31
23 36
31 45
6 39
4 8
13 37
42 48
17 45
19 33
12 21
19 32
16 43
12 47
25 31
40 48
8 49
43 48
6 42
27 34
13 39
17 40
13 35
3 49
20 24
5 12
43 44
15 37
24 27
8 43
4 22
17 38
28 47
29 46
3 15
9 49
1 41
43 45
3 6
37 48
13 30
11 43
8 25
33 38
16 32
32 41

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

100 4900
64 78
3 13
93 96
48 64
34 64
5 76
66 74
44 78
17 20
30 73
5 34
24 100
23 65
4 70
22 95
47 70
6 89
15 70
70 82
88 90
29 80
27 64
16 59
28 99
67 68
85 99
37 85
8 46
71 78
40 95
6 21
27 66
16 89
11 83
17 57
19 36
21 70
27 86
27 45
5 56
10 64
23 33
87 91
37 40
21 55
75 79
54 96
3 77
70 78
36 93...

output:

3689634

result:

ok 1 number(s): "3689634"

Test #5:

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

input:

100 4000
73 78
38 98
9 65
43 72
20 47
6 37
49 60
48 87
48 77
23 100
57 59
42 99
40 88
20 96
19 44
35 80
12 93
34 44
63 75
3 49
32 99
47 61
3 13
54 81
55 96
16 74
28 77
43 45
25 92
5 82
3 83
9 55
64 78
39 89
19 64
58 75
1 18
22 76
16 55
18 60
14 55
29 96
37 97
26 97
11 53
24 79
7 35
53 54
31 74
31 32...

output:

1094294

result:

ok 1 number(s): "1094294"

Test #6:

score: 0
Accepted
time: 91ms
memory: 4788kb

input:

447 99681
346 391
18 307
271 438
50 436
84 215
64 104
291 325
278 355
152 228
7 117
174 410
61 386
7 204
264 327
366 409
291 405
42 131
89 203
1 175
229 292
225 320
1 310
89 185
161 340
401 406
265 377
119 313
253 403
190 383
305 367
334 424
88 327
77 357
25 334
56 62
68 245
1 13
290 336
94 354
10 3...

output:

1641247665

result:

ok 1 number(s): "1641247665"

Test #7:

score: 0
Accepted
time: 90ms
memory: 4880kb

input:

447 99680
18 328
31 202
168 227
55 255
105 321
262 407
38 140
13 65
288 302
26 337
106 358
7 157
237 343
56 410
217 263
62 392
314 345
1 166
96 376
138 410
98 424
202 251
229 429
160 197
175 238
125 312
32 93
281 291
67 99
32 156
33 65
377 445
56 293
64 170
236 423
246 400
61 356
194 430
243 381
205...

output:

1641148875

result:

ok 1 number(s): "1641148875"

Test #8:

score: 0
Accepted
time: 86ms
memory: 4864kb

input:

447 99679
123 230
116 120
218 291
84 132
158 204
31 75
390 395
140 379
34 285
12 67
325 409
24 349
282 342
68 380
81 269
6 55
35 192
314 358
68 438
159 281
118 324
157 211
7 198
376 400
262 335
226 348
305 380
65 434
157 164
111 303
183 338
11 77
44 212
267 279
132 300
145 171
313 416
97 201
50 422
...

output:

1641050086

result:

ok 1 number(s): "1641050086"

Test #9:

score: 0
Accepted
time: 85ms
memory: 4828kb

input:

447 99650
198 335
78 438
83 220
267 280
102 135
98 317
22 84
259 362
57 109
22 162
52 210
160 339
34 75
88 397
381 402
99 276
227 242
205 232
74 299
139 314
238 442
157 229
170 273
44 418
8 30
22 345
39 67
32 298
227 270
93 308
372 424
110 272
409 429
59 107
10 216
193 424
171 320
283 302
261 445
90...

output:

1638188297

result:

ok 1 number(s): "1638188297"

Test #10:

score: 0
Accepted
time: 91ms
memory: 4992kb

input:

447 99600
38 388
94 209
38 420
213 444
324 337
212 444
100 400
153 193
247 252
31 352
156 300
65 384
193 254
8 277
36 181
44 407
111 377
62 226
182 413
113 206
118 344
65 78
200 210
30 214
4 6
271 424
69 119
331 348
93 344
163 178
216 386
349 386
176 219
15 446
147 185
35 368
94 163
204 382
365 443
...

output:

1633262630

result:

ok 1 number(s): "1633262630"

Test #11:

score: 0
Accepted
time: 89ms
memory: 4988kb

input:

447 99500
269 280
220 396
23 62
82 361
384 437
210 358
235 421
194 280
23 293
27 355
36 401
10 329
400 430
148 402
96 301
269 319
259 325
367 427
39 298
263 273
245 369
56 112
71 264
256 323
27 199
323 429
177 209
413 431
108 158
9 98
17 378
182 339
26 414
60 349
73 296
235 357
52 145
333 411
145 14...

output:

1623449253

result:

ok 1 number(s): "1623449253"

Test #12:

score: 0
Accepted
time: 85ms
memory: 4756kb

input:

447 99000
206 301
201 223
266 337
150 435
13 383
136 378
207 225
199 385
107 230
114 400
354 396
158 238
253 319
34 367
293 352
246 398
329 374
86 107
45 442
239 315
230 403
343 387
153 169
178 436
14 235
219 394
261 371
92 381
245 358
10 79
295 370
159 257
324 439
323 411
113 123
195 414
159 186
13...

output:

1575114565

result:

ok 1 number(s): "1575114565"

Test #13:

score: 0
Accepted
time: 82ms
memory: 4840kb

input:

447 98000
143 381
232 430
143 310
52 106
218 311
208 333
256 407
114 228
3 173
82 129
45 78
22 242
42 442
370 371
40 447
205 329
23 281
119 125
265 430
259 365
57 409
160 349
21 339
120 137
44 332
10 93
257 261
191 439
16 144
57 62
34 337
159 308
121 163
1 8
9 233
147 233
295 414
62 143
220 234
28 1...

output:

1481993488

result:

ok 1 number(s): "1481993488"

Test #14:

score: 0
Accepted
time: 79ms
memory: 4724kb

input:

447 90000
111 237
68 388
20 135
42 68
265 326
174 215
192 278
32 418
293 296
164 206
255 296
101 215
93 422
213 257
122 310
367 393
146 165
24 48
121 214
392 400
6 14
166 360
118 267
343 352
336 350
391 424
64 381
207 302
119 379
78 435
248 317
310 385
198 227
105 410
93 220
5 116
214 304
283 432
59...

output:

889086208

result:

ok 1 number(s): "889086208"

Test #15:

score: 0
Accepted
time: 71ms
memory: 4696kb

input:

447 89000
14 240
211 327
221 367
226 346
224 288
20 426
54 412
8 404
77 89
109 330
180 260
373 377
212 315
162 329
9 308
286 301
46 202
52 117
107 412
220 376
50 427
49 138
20 432
153 206
61 280
195 378
25 45
90 114
335 441
191 284
299 365
350 422
203 214
1 311
17 337
55 400
52 262
104 296
261 309
6...

output:

831285099

result:

ok 1 number(s): "831285099"

Test #16:

score: 0
Accepted
time: 83ms
memory: 4956kb

input:

450 100000
83 266
69 103
101 443
43 156
223 271
85 398
99 124
170 400
337 449
206 306
50 59
83 382
52 289
58 332
43 117
299 378
241 273
126 435
353 370
6 439
14 42
19 212
28 198
37 412
227 443
13 204
194 296
108 253
4 354
27 64
13 154
40 102
67 173
106 148
366 425
105 108
155 179
194 372
282 389
249...

output:

1585848605

result:

ok 1 number(s): "1585848605"

Test #17:

score: 0
Accepted
time: 90ms
memory: 4872kb

input:

455 100000
83 297
349 436
200 238
100 403
140 204
111 180
185 380
140 356
213 257
79 409
36 376
221 253
108 218
113 385
270 438
264 355
156 451
387 449
70 96
112 398
40 358
43 160
126 354
9 81
204 277
27 209
35 397
356 389
106 359
245 320
384 406
40 403
107 296
177 206
65 256
261 325
125 369
377 424...

output:

1451687918

result:

ok 1 number(s): "1451687918"

Test #18:

score: 0
Accepted
time: 84ms
memory: 4960kb

input:

500 100000
191 311
182 488
75 292
255 478
2 303
23 70
241 272
104 183
205 292
15 360
385 460
30 49
86 90
278 346
435 444
207 479
106 493
191 226
97 429
123 284
141 498
245 469
195 418
162 261
314 393
428 494
49 247
178 397
375 492
41 83
161 464
60 340
16 223
20 331
62 334
91 244
446 456
374 451
32 1...

output:

682545705

result:

ok 1 number(s): "682545705"

Test #19:

score: 0
Accepted
time: 86ms
memory: 4980kb

input:

550 100000
103 549
183 219
188 502
35 62
26 97
189 213
100 478
338 540
87 504
458 490
241 440
33 477
119 385
160 265
92 182
181 309
110 532
357 383
252 460
152 205
125 466
444 543
52 334
219 302
8 488
48 461
102 252
126 427
185 320
244 417
183 257
216 250
35 127
223 358
64 159
34 441
289 425
308 414...

output:

318745782

result:

ok 1 number(s): "318745782"

Test #20:

score: 0
Accepted
time: 82ms
memory: 4936kb

input:

600 100000
233 309
98 416
259 338
356 539
360 554
364 367
27 256
28 381
107 600
369 424
40 444
533 597
384 588
306 532
98 248
484 574
113 347
273 447
131 369
119 176
328 358
30 460
32 278
388 415
313 423
52 94
475 533
80 351
213 344
37 175
73 129
47 596
171 294
313 436
295 495
183 189
486 547
87 146...

output:

158555444

result:

ok 1 number(s): "158555444"

Test #21:

score: 0
Accepted
time: 78ms
memory: 5052kb

input:

650 100000
105 412
198 265
123 593
94 515
201 403
463 603
51 382
114 281
440 614
193 461
372 499
130 333
312 371
276 421
83 543
299 540
60 354
402 522
175 190
95 373
72 285
482 536
382 507
419 595
383 599
98 379
101 584
272 326
69 455
361 583
331 595
541 552
77 514
163 623
228 235
232 239
241 381
32...

output:

83601361

result:

ok 1 number(s): "83601361"

Test #22:

score: 0
Accepted
time: 67ms
memory: 4928kb

input:

700 100000
300 467
95 626
137 167
85 441
44 308
99 601
52 550
448 504
127 352
133 584
192 239
230 687
407 604
106 398
215 491
103 203
330 690
450 460
251 264
291 521
38 296
347 406
17 577
337 700
30 375
238 659
230 476
77 163
87 474
296 384
202 624
22 474
34 682
105 194
307 349
415 492
548 596
333 5...

output:

46181798

result:

ok 1 number(s): "46181798"

Test #23:

score: 0
Accepted
time: 62ms
memory: 4984kb

input:

750 100000
133 309
210 581
101 409
279 540
291 579
150 187
390 615
107 729
266 438
71 644
589 645
683 716
79 508
100 101
177 377
310 400
46 245
468 728
481 702
509 511
67 268
192 224
116 308
284 588
429 672
303 387
371 380
503 624
161 631
223 409
315 750
138 293
26 78
448 450
483 536
95 391
399 455
...

output:

26665209

result:

ok 1 number(s): "26665209"

Test #24:

score: 0
Accepted
time: 49ms
memory: 4896kb

input:

800 100000
596 779
65 391
266 531
3 429
409 428
386 525
235 274
182 189
610 620
338 623
209 455
408 534
173 762
145 761
347 771
25 796
240 703
299 577
567 672
678 777
390 577
405 693
470 610
456 659
124 595
153 533
416 700
121 673
161 417
315 513
20 444
129 448
120 737
178 195
94 758
91 651
10 264
1...

output:

15871497

result:

ok 1 number(s): "15871497"

Test #25:

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

input:

850 100000
168 401
190 479
479 654
298 365
19 389
395 721
486 641
586 812
148 820
501 772
143 536
17 746
201 722
190 590
250 690
456 458
391 847
608 723
718 800
7 684
243 771
131 608
299 706
225 391
311 619
228 486
419 725
245 262
303 349
604 758
283 533
72 91
528 687
261 545
418 707
55 730
439 500
...

output:

9738714

result:

ok 1 number(s): "9738714"

Test #26:

score: 0
Accepted
time: 43ms
memory: 4808kb

input:

900 100000
230 313
384 846
107 330
715 832
24 474
6 234
146 210
399 517
131 471
353 732
109 218
363 829
108 165
350 705
155 549
618 657
826 847
649 740
224 858
132 586
194 745
420 622
215 516
422 436
43 339
471 857
214 477
469 661
232 881
79 615
138 537
352 466
66 441
636 803
740 802
205 248
235 400...

output:

6178526

result:

ok 1 number(s): "6178526"

Test #27:

score: 0
Accepted
time: 33ms
memory: 4848kb

input:

950 100000
870 880
831 846
695 706
482 826
147 483
316 867
148 853
57 435
328 435
207 535
136 393
710 801
230 684
59 569
698 717
170 289
218 879
84 168
216 793
161 718
227 728
24 594
40 583
304 829
247 932
254 778
266 855
203 502
381 806
93 149
829 934
760 890
417 757
391 940
397 530
195 669
72 278
...

output:

4007438

result:

ok 1 number(s): "4007438"

Test #28:

score: 0
Accepted
time: 25ms
memory: 4860kb

input:

1000 100000
151 908
468 726
148 744
360 767
335 500
29 147
510 572
173 872
190 221
505 703
559 828
245 493
531 975
155 526
31 927
506 589
268 641
195 285
462 774
347 964
495 838
139 920
149 667
932 984
385 696
336 415
150 634
97 204
318 498
430 436
426 637
399 845
219 419
530 968
147 497
41 654
377 ...

output:

2663248

result:

ok 1 number(s): "2663248"

Test #29:

score: 0
Accepted
time: 22ms
memory: 4772kb

input:

1200 100000
1062 1129
179 345
580 735
440 1169
27 869
345 689
742 1069
786 973
822 831
231 998
202 586
95 150
317 834
494 927
431 685
38 144
662 1001
204 537
912 962
128 753
627 670
158 175
531 980
836 895
370 1095
61 999
939 1025
268 494
244 612
608 701
378 1180
182 1047
165 656
355 922
262 1055
44...

output:

620725

result:

ok 1 number(s): "620725"

Test #30:

score: 0
Accepted
time: 26ms
memory: 4656kb

input:

1500 100000
134 1417
166 340
168 685
1028 1152
360 401
304 1312
383 1271
952 1313
228 1285
1142 1209
199 630
551 1450
34 612
1215 1287
1303 1359
654 1455
548 828
158 1244
154 699
344 478
1107 1288
14 34
213 342
450 1387
390 855
150 1373
864 1368
437 773
775 917
399 759
7 404
504 1083
1018 1116
1087 ...

output:

103169

result:

ok 1 number(s): "103169"

Test #31:

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

input:

2000 100000
293 774
432 1543
41 1141
886 958
849 1173
413 1564
1230 1393
1267 1735
1050 1097
170 442
515 807
1372 1799
583 723
221 1277
363 1668
39 1600
1215 1663
51 1861
254 1813
1397 1563
1090 1205
42 214
101 742
1682 1714
846 1321
480 820
524 1925
942 1161
749 1443
957 1651
1011 1827
411 1583
298...

output:

10492

result:

ok 1 number(s): "10492"

Test #32:

score: 0
Accepted
time: 38ms
memory: 4916kb

input:

4000 100000
312 660
371 2160
2846 3208
231 599
3282 3670
670 3822
649 1836
2302 2487
880 3548
250 3435
2850 3222
3297 3806
87 203
573 2073
1152 1617
1458 3254
1039 2669
1750 2452
230 433
1634 2462
263 3969
2182 3233
779 3440
2360 3247
52 3051
1876 3481
187 1125
2391 2559
1434 2120
830 3575
186 2738
...

output:

28

result:

ok 1 number(s): "28"

Test #33:

score: 0
Accepted
time: 57ms
memory: 5188kb

input:

5000 100000
2274 3651
2477 3599
3918 3972
2918 3912
2111 4134
2171 4230
312 3009
2078 4938
2886 4282
2101 3295
1213 1420
1834 3289
2389 3817
4411 4536
3269 4685
2989 4628
4298 4380
715 2013
1121 1909
2110 4232
428 1063
818 2709
168 446
1133 4182
2291 3799
3298 4558
172 1829
487 4243
2252 3744
1615 1...

output:

10

result:

ok 1 number(s): "10"

Test #34:

score: 0
Accepted
time: 62ms
memory: 5432kb

input:

7000 100000
1 1348
1 1515
1 1679
1 2152
1 2628
1 2834
1 3090
1 3199
1 3605
1 3733
1 3770
1 4162
1 4293
1 4328
1 4610
1 4660
1 4729
1 4749
1 4937
1 5023
1 5761
1 5957
1 6018
1 6027
1 6374
1 6429
1 6533
1 6717
1 6755
1 6899
2 428
2 704
2 794
2 1153
2 1338
2 1383
2 1544
2 1636
2 1674
2 1887
2 2507
2 28...

output:

1

result:

ok 1 number(s): "1"

Test #35:

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

input:

10000 100000
1 599
1 631
1 748
1 1328
1 1448
1 1537
1 1550
1 2002
1 3744
1 3946
1 5152
1 5171
1 6203
1 6390
1 6494
1 7243
1 7575
1 7721
1 8982
1 9550
2 433
2 601
2 1764
2 2043
2 2072
2 2431
2 2551
2 3911
2 4083
2 4167
2 4647
2 5315
2 5964
2 6704
2 7216
2 7426
2 8338
2 8475
2 8856
2 9758
3 22
3 501
3...

output:

0

result:

ok 1 number(s): "0"

Test #36:

score: 0
Accepted
time: 382ms
memory: 6208kb

input:

15000 100000
1 65
1 2527
1 2746
1 3303
1 3787
1 4152
1 5174
1 5527
1 5592
1 7593
1 8008
1 10468
1 12196
1 12497
2 1118
2 3411
2 5578
2 7535
2 9993
2 13529
2 14170
3 379
3 1834
3 2224
3 3963
3 4463
3 6263
3 7627
3 9859
3 14540
4 202
4 931
4 3140
4 3500
4 7443
4 8516
4 8924
4 9011
4 9161
4 9305
4 9806...

output:

0

result:

ok 1 number(s): "0"

Test #37:

score: 0
Accepted
time: 759ms
memory: 6792kb

input:

20000 100000
1 494
1 3337
1 5325
1 6842
1 8285
1 9909
1 15624
1 16511
1 19010
2 473
2 5509
2 6781
2 7657
2 11080
2 13540
2 14056
2 14100
3 519
3 610
3 769
3 1520
3 4714
3 6023
3 10084
3 11846
3 12525
3 13207
3 13278
3 14269
3 16105
3 17724
3 17730
4 651
4 3950
4 7055
4 7109
4 7189
4 7943
4 9843
4 12...

output:

0

result:

ok 1 number(s): "0"

Test #38:

score: -100
Time Limit Exceeded

input:

25000 100000
1 2780
1 3697
1 4022
1 9754
1 15416
1 22314
2 1261
2 4159
2 10565
2 14313
2 20192
3 4057
3 5300
3 9652
3 10257
3 12853
3 16487
3 18000
3 19268
3 21416
3 21519
4 4200
4 5341
4 5821
4 11263
4 12131
4 15166
4 15604
4 17008
4 19379
5 2911
5 8394
5 14484
5 17755
5 19720
5 21274
5 23969
6 132...

output:


result: