QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153466 | #6354. 4 | nicksms | TL | 759ms | 6792kb | C++17 | 1.4kb | 2023-08-30 05:17:19 | 2023-08-30 05:17:19 |
Judging History
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...