QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200344 | #7343. Bicycle Race | Team_name# | WA | 1067ms | 160176kb | C++20 | 1.9kb | 2023-10-04 16:33:34 | 2023-10-04 16:33:35 |
Judging History
answer
#include <bitset>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
constexpr int N = 1E5, M = 1E5;
constexpr int B = 10000;
int u[M], v[M]; int a[M];
std::unordered_map<int, int> a_[N];
std::bitset<B> to[N];
std::vector<int> C[N];
int calc(int w, int i)
{
return a_[w][u[i]] + a[i] + a_[v[i]][w];
}
bool intersect(int i, int j)
{
return u[i] == u[j] || u[i] == v[j] || v[i] == u[j] || v[i] == v[j];
}
void chk_max(int& a, int b) { if (a < b) a = b; }
int main()
{
std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);
int n, m; std::cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int& u = ::u[i], & v = ::v[i];
std::cin >> u >> v >> a[i];
--u;
--v;
a_[u][v] = a_[v][u] = a[i];
}
for (int l = 0, r; l < n; l = r)
{
r = l + B;
for (int i = 0; i < n; ++i)
to[i].reset();
for (int i = 0; i < m; ++i)
{
if (l <= v[i] && v[i] < r)
to[u[i]].set(v[i] - l);
if (l <= u[i] && u[i] < r)
to[v[i]].set(u[i] - l);
}
for (int i = 0; i < m; ++i)
{
auto&& s = to[u[i]] & to[v[i]];
for (int j = s._Find_first(); j < B; j = s._Find_next(j))
C[j].push_back(i);
}
}
int ans = -1;
for (int i = 0; i < n; ++i)
{
auto& C = ::C[i];
if (C.size() < 2) continue;
int m = 0;
for (int j = 0; j < C.size(); ++j)
if (int s = calc(i, C[j]); s > m)
m = s, std::swap(C[0], C[j]);
m = 0;
for (int j = 1; j < C.size(); ++j)
if (int s = calc(i, C[j]); s > m)
m = s, std::swap(C[1], C[j]);
if (!intersect(C[0], C[1]))
chk_max(ans, calc(i, C[0]) + calc(i, C[1]));
else
{
int s = calc(i, C[0]);
for (int j = 2; j < C.size(); ++j)
if (!intersect(C[0], C[j]))
chk_max(ans, s + calc(i, C[j]));
s = calc(i, C[1]);
for (int j = 2; j < C.size(); ++j)
if (!intersect(C[1], C[j]))
chk_max(ans, s + calc(i, C[j]));
}
}
std::cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13816kb
input:
6 9 1 2 3 2 3 1 3 4 2 4 5 1 3 5 7 2 5 2 1 5 3 4 6 2 5 6 1
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 2ms
memory: 13708kb
input:
6 6 1 3 2 1 2 2 2 3 4 3 4 1 3 6 6 1 4 8
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 13944kb
input:
5 6 1 4 2 1 3 6 5 2 10 3 2 4 4 2 1 5 4 7
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 3ms
memory: 13476kb
input:
5 10 2 1 9 3 1 4 3 2 3 4 1 5 4 2 9 4 3 9 5 1 5 5 2 6 5 3 10 5 4 1
output:
43
result:
ok 1 number(s): "43"
Test #5:
score: 0
Accepted
time: 2ms
memory: 14512kb
input:
5 10 2 1 9 3 1 8 3 2 8 4 1 1 4 2 2 4 3 8 5 1 10 5 2 1 5 3 10 5 4 3
output:
46
result:
ok 1 number(s): "46"
Test #6:
score: 0
Accepted
time: 0ms
memory: 13732kb
input:
5 9 1 3 4 4 1 10 1 5 9 5 2 9 3 5 9 2 3 7 5 4 1 2 1 7 2 4 1
output:
45
result:
ok 1 number(s): "45"
Test #7:
score: 0
Accepted
time: 0ms
memory: 13268kb
input:
5 8 2 1 10 5 2 5 1 3 7 3 5 8 3 2 5 2 4 6 4 3 5 4 5 6
output:
41
result:
ok 1 number(s): "41"
Test #8:
score: 0
Accepted
time: 3ms
memory: 13672kb
input:
200 2000 182 97 91166 25 11 25393 179 58 43378 77 41 75588 139 96 94145 135 56 4609 190 159 47293 100 30 33854 21 132 93072 174 135 93547 144 137 81216 199 102 68247 89 155 53788 83 25 64607 166 179 44534 101 3 1474 37 106 57970 187 41 19892 16 76 32024 182 13 32061 72 69 5823 187 185 13918 151 86 3...
output:
552426
result:
ok 1 number(s): "552426"
Test #9:
score: 0
Accepted
time: 4ms
memory: 13908kb
input:
400 4000 102 372 24346 360 153 94255 272 316 33427 215 71 52304 368 202 60854 350 206 16796 32 372 31489 109 14 95840 163 71 79896 330 393 95303 324 110 13216 197 341 69668 54 241 46100 222 246 67388 140 13 539 272 79 22065 389 221 81398 187 122 60482 198 352 4291 196 14 18220 215 93 64141 336 54 54...
output:
545402
result:
ok 1 number(s): "545402"
Test #10:
score: 0
Accepted
time: 2ms
memory: 13924kb
input:
600 6000 270 248 73879 94 543 63116 118 174 23476 152 301 12668 597 557 27564 566 156 28983 322 585 15685 319 598 41474 506 411 50369 334 450 80707 103 83 61569 195 333 71089 219 576 54764 409 18 70169 115 296 72896 92 155 42655 542 537 4827 387 202 1071 209 15 4380 511 165 22459 485 571 94537 570 2...
output:
545966
result:
ok 1 number(s): "545966"
Test #11:
score: 0
Accepted
time: 3ms
memory: 16356kb
input:
800 8000 391 123 23412 629 133 31977 411 31 13525 489 131 89384 427 512 94273 29 506 24818 564 397 99881 528 382 3460 448 702 20841 290 156 82464 235 56 9922 192 772 88862 784 63 47076 148 591 72950 490 531 45253 263 231 63246 295 453 44608 234 683 58012 562 56 32475 671 464 90539 454 237 97128 635 ...
output:
537316
result:
ok 1 number(s): "537316"
Test #12:
score: 0
Accepted
time: 7ms
memory: 16828kb
input:
900 9000 751 713 98178 420 281 8232 734 560 50374 234 645 19566 641 65 77628 537 681 89087 561 4 33803 457 274 26277 367 372 56077 816 485 16990 425 42 67747 543 144 89573 43 230 93232 441 701 66164 801 772 31431 773 392 73541 771 535 6323 634 271 20131 429 870 52257 54 265 33619 425 148 84463 285 6...
output:
543761
result:
ok 1 number(s): "543761"
Test #13:
score: 0
Accepted
time: 7ms
memory: 16548kb
input:
1000 10000 474 791 31535 814 802 77941 268 530 73504 935 202 16680 294 563 90749 295 865 28879 881 407 92656 170 489 69207 647 539 16716 588 994 32698 450 999 67004 450 85 62626 88 759 97603 375 910 48465 855 380 62615 581 791 48023 692 533 10312 249 752 93019 229 570 80407 135 31 24826 158 458 2555...
output:
535602
result:
ok 1 number(s): "535602"
Test #14:
score: 0
Accepted
time: 1067ms
memory: 160176kb
input:
500 100000 2 1 54424 3 1 48973 3 2 86095 4 1 76564 4 2 82172 4 3 86663 5 1 24522 5 2 37933 5 3 67602 5 4 17497 6 1 53084 6 2 41172 6 3 52523 6 4 91108 6 5 84953 7 1 594 7 2 61541 7 3 90638 7 4 34896 7 5 73592 7 6 62931 8 2 72346 8 5 16373 8 7 95438 9 1 19930 9 2 89438 9 3 2195 9 4 71744 9 5 1168 9 6...
output:
596558
result:
ok 1 number(s): "596558"
Test #15:
score: 0
Accepted
time: 1031ms
memory: 159100kb
input:
500 100000 2 1 2692 3 2 10621 4 1 60135 4 2 56741 5 1 66724 5 2 46777 5 3 72456 5 4 41383 6 1 24952 6 2 86 6 3 50877 6 4 14549 6 5 12700 7 1 81676 7 2 72840 7 3 96493 7 5 75581 7 6 97962 8 2 35448 8 3 48547 8 4 38631 8 5 82104 8 6 23747 8 7 36514 9 1 48937 9 2 11326 9 3 69303 9 4 82858 9 5 63680 9 6...
output:
597511
result:
ok 1 number(s): "597511"
Test #16:
score: 0
Accepted
time: 53ms
memory: 35528kb
input:
10000 100000 2188 6529 2 2188 7677 2 2188 7805 2 2188 9308 2 6529 7677 2 7805 9308 2 9599 3197 1 1786 3787 1 3578 3237 1 4859 8184 1 5300 3418 1 8450 499 1 8636 8041 1 8387 362 1 2902 1224 1 4847 1610 1 1619 3629 1 1694 5617 1 12 9337 1 4295 2005 1 6636 8226 1 9375 8605 1 9768 4222 1 2699 3741 1 537...
output:
12
result:
ok 1 number(s): "12"
Test #17:
score: 0
Accepted
time: 46ms
memory: 35712kb
input:
10000 100000 4562 1795 2 4562 2711 2 4562 3418 2 4562 5389 2 1795 2711 2 3418 5389 2 5748 3255 1 4941 6175 1 4685 7745 1 9064 5340 1 8299 8951 1 6060 4991 1 8897 6685 1 3518 4129 1 1106 6438 1 7695 3588 1 5920 5482 1 3070 9224 1 2582 5878 1 6686 8890 1 4017 4816 1 1282 4041 1 4601 436 1 2500 1638 1 ...
output:
12
result:
ok 1 number(s): "12"
Test #18:
score: 0
Accepted
time: 57ms
memory: 35400kb
input:
10000 100000 6937 2540 2 6937 2679 2 6937 6749 2 6937 7929 2 2540 2679 2 6749 7929 2 1897 3312 1 1744 4915 1 5791 8605 1 3268 6145 1 7651 4484 1 22 9483 1 9159 5330 1 8649 7897 1 9309 1651 1 543 5566 1 222 3688 1 4447 6479 1 1504 8771 1 9076 2126 1 7750 5054 1 3189 9477 1 3082 6651 1 2300 3183 1 315...
output:
12
result:
ok 1 number(s): "12"
Test #19:
score: 0
Accepted
time: 17ms
memory: 32208kb
input:
10000 29992 1 2 1 9997 1 1 9998 1 1 2 3 1 9997 2 1 9998 2 1 3 4 1 9997 3 1 9998 3 1 4 5 1 9997 4 1 9998 4 1 5 6 1 9997 5 1 9998 5 1 6 7 1 9997 6 1 9998 6 1 7 8 1 9997 7 1 9998 7 1 8 9 1 9997 8 1 9998 8 1 9 10 1 9997 9 1 9998 9 1 10 11 1 9997 10 1 9998 10 1 11 12 1 9997 11 1 9998 11 1 12 13 1 9997 12...
output:
100302
result:
ok 1 number(s): "100302"
Test #20:
score: 0
Accepted
time: 0ms
memory: 27388kb
input:
10000 9999 4324 1 16290 4324 2 71785 4324 3 14388 4324 4 8277 4324 5 13642 4324 6 51181 4324 7 26874 4324 8 209 4324 9 38258 4324 10 6368 4324 11 35018 4324 12 17125 4324 13 36915 4324 14 13046 4324 15 16002 4324 16 33080 4324 17 60494 4324 18 35992 4324 19 95076 4324 20 71293 4324 21 81397 4324 22 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #21:
score: 0
Accepted
time: 247ms
memory: 153544kb
input:
100000 99999 58495 1 85101 58495 2 97799 58495 3 80649 58495 4 34353 58495 5 87833 58495 6 34007 58495 7 83178 58495 8 67343 58495 9 53763 58495 10 62046 58495 11 59552 58495 12 58790 58495 13 68682 58495 14 98674 58495 15 75531 58495 16 46217 58495 17 59944 58495 18 28555 58495 19 26879 58495 20 69...
output:
-1
result:
ok 1 number(s): "-1"
Test #22:
score: 0
Accepted
time: 5ms
memory: 27552kb
input:
10000 9999 9886 6478 77145 6478 1002 22410 1002 7725 6914 7725 5151 88423 5151 4615 90706 4615 276 88418 276 651 31102 651 3396 17550 3396 7197 47149 7197 1517 57637 1517 2551 26825 2551 1399 97972 1399 3669 37991 3669 1030 41452 1030 7296 58441 7296 7481 50595 7481 7754 56414 7754 6401 80568 6401 3...
output:
-1
result:
ok 1 number(s): "-1"
Test #23:
score: 0
Accepted
time: 361ms
memory: 152320kb
input:
100000 99999 99697 62499 17359 62499 65369 84138 65369 38767 3834 38767 49004 92149 49004 41714 87272 41714 25240 48039 25240 40929 14513 40929 74271 5375 74271 97963 48998 97963 88205 97714 88205 44238 78637 44238 73947 33673 73947 88038 12339 88038 34453 65123 34453 94958 19816 94958 48075 10067 4...
output:
-1
result:
ok 1 number(s): "-1"
Test #24:
score: 0
Accepted
time: 0ms
memory: 16352kb
input:
100 197 60 98 1617 98 3 35314 98 8 32959 98 67 38073 8 46 43213 3 31 95978 46 64 29598 8 12 83873 31 74 37874 64 16 69419 8 100 8340 8 81 32173 8 75 36960 100 14 87509 74 84 76405 46 91 52507 16 5 76978 81 41 10067 41 71 51697 14 99 1009 75 9 49341 5 35 41721 9 88 26833 100 79 8899 12 15 86030 31 76...
output:
509330
result:
ok 1 number(s): "509330"
Test #25:
score: 0
Accepted
time: 3ms
memory: 16488kb
input:
1000 1997 657 656 12140 657 103 50769 656 608 43803 103 457 76249 608 620 90055 657 222 58123 656 331 97872 331 930 58126 103 90 90000 656 987 97497 331 793 66164 457 690 43735 656 929 32424 222 205 54505 103 124 69291 793 274 59946 103 333 94914 205 831 90318 656 78 78344 930 267 11779 274 606 2928...
output:
547289
result:
ok 1 number(s): "547289"
Test #26:
score: 0
Accepted
time: 18ms
memory: 31224kb
input:
10000 19997 9886 6478 22410 9886 1002 88423 1002 7725 88418 1002 5151 17550 7725 4615 57637 5151 276 97972 276 651 41452 4615 3396 50595 1002 7197 80568 6478 1517 46843 7725 2551 11832 4615 1399 32622 6478 3669 13880 4615 1030 96284 1030 7296 27398 5151 7481 33479 276 7754 10690 9886 6401 20178 2551...
output:
580069
result:
ok 1 number(s): "580069"
Test #27:
score: -100
Wrong Answer
time: 217ms
memory: 96136kb
input:
50000 99997 46703 3202 33177 3202 23493 62517 23493 17355 31588 17355 11839 13616 11839 40451 67170 17355 19209 39727 46703 41048 46860 40451 12518 58874 46703 24389 57287 40451 41038 57317 23493 34738 13193 11839 1865 32227 12518 44478 5445 40451 36110 58217 19209 20878 24949 1865 13239 40449 46703...
output:
273110
result:
wrong answer 1st numbers differ - expected: '589408', found: '273110'