QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #875645 | #2746. Highway Tolls | Wansur | 0 | 291ms | 24048kb | C++20 | 2.8kb | 2025-01-30 00:24:33 | 2025-01-30 00:24:34 |
Judging History
answer
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 12;
vector<pair<int, int>> g[maxn];
ll d1[maxn], d2[maxn];
ll a, b;
int n, m;
int pos = -1;
vector<array<int, 3>> bfs(int v, ll d[]) {
vector<array<int, 3>> res;
for(int i = 0; i < n; i++) {
if(d[i] >= 0) {
d[i] = 1e18;
}
}
d[v] = 0;
queue<int> q;
res.push_back({v, v, -1});
q.push(v);
while(q.size()) {
int u = q.front();
q.pop();
for(auto [to, id] : g[u]) {
if(id <= pos) continue;
if(d[to] > d[u] + 1) {
q.push(to);
d[to] = d[u] + 1;
res.push_back({u, to, id});
}
}
}
return res;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N, m = (int)U.size();
a = A, b = B;
for(int i = 0; i < m; i++) {
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
}
ll len = ask(vector<int> (m, 0));
len /= a;
for(int l = 0, r = m - 1; l <= r;) {
int mid = (l + r) >> 1;
vector<int> w(m, 0);
for(int i = 0; i <= mid; i++) {
w[i] = 1;
}
if(ask(w) > len * a) {
pos = mid;
r = mid - 1;
}
else l = mid + 1;
}
vector<int> ww(m, 0);
ww[0] = 1;
bfs(U[pos], d1);
bfs(V[pos], d2);
vector<int> s, t;
for(int i = 0; i < n; i++) {
if(d1[i] < d2[i]) {
s.push_back(i);
}
if(d2[i] < d1[i]) {
t.push_back(i);
}
if(d1[i] < d2[i]) d2[i] = -1;
else if(d2[i] < d1[i]) d1[i] = -1;
}
auto ord = bfs(U[pos], d1);
auto orz = bfs(V[pos], d2);
int u = -1, v = -1;
for(int l = 0, r = (int)ord.size() - 1; l <= r;) {
int mid = (l + r) >> 1;
vector<int> w(m, 0);
for(int i = 1; i < ord.size(); i++) {
w[ord[i][2]] = (i > mid);
}
for(int i = 0; i < pos; i++) {
w[i] = 1;
}
if(ask(w) == len * a) {
u = ord[mid][1];
r = mid - 1;
}
else l = mid + 1;
}
for(int l = 0, r = (int)orz.size() - 1; l <= r;) {
int mid = (l + r) >> 1;
vector<int> w(m, 0);
for(int i = 1; i < orz.size(); i++) {
w[orz[i][2]] = (i > mid);
}
for(int i = 0; i < pos; i++) {
w[i] = 1;
}
if(ask(w) == len * a) {
v = orz[mid][1];
r = mid - 1;
}
else l = mid + 1;
}
assert(u != U[pos] && u != V[pos]);
answer(u, v);
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 5
Accepted
time: 0ms
memory: 3840kb
input:
100 99 1 2 0 75 15 17 47 98 19 41 22 51 38 7 96 5 47 75 28 12 6 0 25 76 0 11 32 66 97 81 23 56 32 94 46 79 18 2 0 3 44 33 89 97 49 31 43 65 56 9 71 93 87 18 12 37 94 34 73 42 66 15 15 8 27 85 3 37 57 28 74 12 69 60 91 24 82 39 60 15 67 78 1 47 19 92 86 75 30 38 86 14 50 96 38 89 50 68 70 52 63 12 12...
output:
Accepted: 15
result:
points 1.0
Test #2:
score: 5
Accepted
time: 1ms
memory: 3840kb
input:
100 99 1 3 0 36 11 81 47 21 71 13 78 32 34 10 82 98 70 67 61 44 86 5 87 41 6 85 64 5 2 62 75 81 84 72 27 13 90 81 53 9 8 24 96 92 5 94 89 58 46 85 63 36 14 88 16 38 35 50 66 16 61 65 1 0 14 71 25 47 45 77 62 5 61 17 94 91 73 34 18 89 91 84 42 31 55 6 28 65 20 13 45 57 82 52 25 71 53 65 24 96 29 70 3...
output:
Accepted: 16
result:
points 1.0
Test #3:
score: 5
Accepted
time: 0ms
memory: 3968kb
input:
99 98 2 3 0 93 70 6 50 24 45 49 11 55 98 84 48 33 39 31 61 84 9 94 57 11 77 5 44 92 88 89 1 13 16 31 15 25 64 25 78 70 51 70 11 0 22 11 48 96 82 62 22 1 63 68 74 49 85 36 11 77 90 72 35 30 91 66 30 57 23 49 22 65 70 42 59 26 7 2 6 22 15 60 43 31 75 40 12 30 37 96 70 71 26 87 76 8 68 81 34 98 72 77 7...
output:
Accepted: 15
result:
points 1.0
Test #4:
score: 0
Runtime Error
input:
99 98 2 5 0 80 43 14 52 42 67 92 53 11 55 90 38 55 51 22 44 94 80 65 94 72 63 84 85 29 82 25 3 92 46 17 1 7 72 40 37 38 20 13 12 23 57 60 49 8 58 42 14 20 65 60 96 71 73 72 17 6 41 82 44 34 15 49 69 86 20 87 67 20 79 6 77 14 21 38 92 36 70 69 67 84 76 41 19 72 10 75 30 82 41 85 35 34 94 83 82 68 72 ...
output:
Unauthorized output
result:
Subtask #2:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
input:
1000 999 1 3 0 874 571 255 559 871 73 988 563 389 502 605 104 306 874 383 591 152 89 697 365 670 830 695 726 652 271 643 284 50 607 442 30 361 579 346 435 799 972 675 310 421 122 47 222 915 343 917 622 336 888 484 48 11 761 419 305 678 504 115 28 121 133 132 369 296 415 982 408 434 24 132 492 764 94...
output:
Unauthorized output
result:
Subtask #3:
score: 0
Runtime Error
Test #27:
score: 0
Runtime Error
input:
10000 9999 1 3 1402 1418 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 ...
output:
Unauthorized output
result:
Subtask #4:
score: 0
Runtime Error
Test #36:
score: 33
Accepted
time: 0ms
memory: 4096kb
input:
1000 999 1 2 685 383 303 325 476 191 222 120 555 130 655 639 211 393 795 613 389 888 960 815 446 325 846 315 51 348 409 82 470 402 681 258 772 969 767 164 290 46 34 887 453 584 142 73 814 603 36 665 701 727 200 702 638 685 33 580 422 859 550 486 849 250 319 144 189 502 140 63 650 765 251 942 304 99 ...
output:
Accepted: 23
result:
points 1.0
Test #37:
score: 33
Accepted
time: 4ms
memory: 5584kb
input:
10000 9999 1 3 1783 6259 7293 57 7709 5040 9728 4012 8079 8209 9430 4904 6390 9228 7715 5997 9936 717 5226 52 9173 3051 7832 7311 6952 8564 6226 7816 433 4639 3438 5850 6341 4537 1863 4404 6454 5466 2929 5366 8417 4118 2366 3037 2780 757 5705 4213 5398 7910 6730 4996 5791 8331 9429 5235 9846 1200 39...
output:
Accepted: 37
result:
points 1.0
Test #38:
score: 0
Runtime Error
input:
70000 69999 2 3 69377 57081 8691 23855 42416 26863 36340 62234 30435 61792 63863 4516 4636 25229 3248 68179 9283 69793 42520 59468 58572 41154 16070 59343 50253 19571 39285 60461 11716 59229 70 21580 59258 28359 46256 31086 1697 10419 6315 30818 43294 44315 12932 67250 47382 45633 60342 37095 20798 ...
output:
Unauthorized output
result:
Subtask #5:
score: 0
Runtime Error
Test #61:
score: 18
Accepted
time: 16ms
memory: 5688kb
input:
10000 11000 1 2 4410 9396 4021 14 6386 7290 4635 4576 1295 5062 8655 8174 3709 4958 7062 1337 6608 2435 9704 3638 5777 2945 1125 365 2861 1023 1560 8478 1423 7827 2638 6211 1429 4399 626 6111 9981 7033 7740 7631 3904 3628 2812 6221 9946 2671 1646 6255 2653 7666 5575 3080 8314 2317 1868 7058 8177 514...
output:
Accepted: 38
result:
points 1.0
Test #62:
score: 18
Accepted
time: 11ms
memory: 5444kb
input:
10000 12000 1 2 8914 2754 434 1136 9173 573 3454 6615 2946 288 3915 3593 3828 6746 6635 665 7131 1042 4342 6970 1127 3292 8034 8501 3356 2570 1952 3736 4431 4448 8634 7879 7196 3553 611 9163 7930 5623 4745 5326 4688 2034 8854 9034 6558 9927 7478 9489 987 1460 141 7334 8768 8671 6973 4170 5359 7289 5...
output:
Accepted: 37
result:
points 1.0
Test #63:
score: 18
Accepted
time: 211ms
memory: 21488kb
input:
90000 100000 1 2 75322 63546 69499 27559 38229 1171 57605 41391 37236 5292 31433 88838 3541 3671 82244 70112 30156 75569 18991 16709 22697 35556 40077 61048 38380 81312 6303 77697 10570 27814 23603 14312 9273 54292 5697 44097 70695 35843 86903 38883 80677 25435 41667 74744 5605 14057 49672 74026 297...
output:
Accepted: 45
result:
points 1.0
Test #64:
score: 18
Accepted
time: 147ms
memory: 21576kb
input:
90000 110000 1 2 74466 67848 68097 22477 20007 34939 28196 24201 80526 63080 20627 81623 12008 46314 16911 53629 49816 193 71014 25845 13945 51574 65448 24107 44331 54812 55021 37430 60283 75844 28330 81393 21311 35513 65936 64670 33857 13492 45048 67079 39197 83746 24176 70511 67941 47342 23434 618...
output:
Accepted: 47
result:
points 1.0
Test #65:
score: 18
Accepted
time: 116ms
memory: 22860kb
input:
90000 130000 1 2 56305 39836 1604 82119 43477 2753 47523 67309 71136 15561 20783 44710 39073 31749 6828 14770 47157 11662 80463 70032 17608 25155 73309 2097 60275 65633 74034 14638 87431 58865 68932 58173 21478 53704 52412 44267 52702 56477 56226 71197 2970 7354 39550 88510 26905 54644 55560 86979 7...
output:
Accepted: 48
result:
points 1.0
Test #66:
score: 18
Accepted
time: 185ms
memory: 24048kb
input:
90000 130000 1 2 63390 29918 43935 67677 64814 71435 7795 86165 9178 14941 49328 26067 87813 3426 41778 47453 3316 27333 68266 87896 89807 74352 30386 69164 19434 74827 12972 47452 88521 54592 20891 32716 86567 2892 61130 13173 75178 34646 9395 58963 13646 4810 73395 42900 70573 42572 66106 1489 823...
output:
Accepted: 49
result:
points 1.0
Test #67:
score: 18
Accepted
time: 139ms
memory: 23856kb
input:
90000 130000 1 2 11022 89395 75693 84971 30696 47119 58426 19067 34383 87899 35529 14786 11402 88537 14569 85256 89788 26671 45642 5813 32553 68443 23961 68708 1437 58824 49694 46233 62923 59227 19534 68125 73800 44065 65575 58256 38526 12890 16338 84303 16848 7588 49529 365 79859 56 76961 25871 356...
output:
Accepted: 48
result:
points 1.0
Test #68:
score: 18
Accepted
time: 156ms
memory: 23852kb
input:
90000 130000 1 2 42568 68186 44784 80303 10319 1023 14043 15412 83359 89919 71326 14771 8602 21355 35485 15804 80662 34042 18358 26369 13635 59420 65758 17748 2070 79076 20146 16442 6084 46290 65228 51742 68485 26027 75950 12124 82601 74582 61984 66774 70563 73800 9064 63841 72933 29722 40428 38750 ...
output:
Accepted: 35
result:
points 1.0
Test #69:
score: 18
Accepted
time: 45ms
memory: 14196kb
input:
32500 129984 1 2 17145 30635 14009 29302 14009 16717 9015 17145 15541 30635 24409 14009 30635 14954 9663 14009 15681 30635 30635 15407 3212 11707 31629 17145 28667 30635 30635 22814 27336 14009 3212 27236 6231 30635 17145 22972 3212 16275 7475 14009 3212 10046 6190 30635 17145 4119 29928 14009 3212 ...
output:
Accepted: 30
result:
points 1.0
Test #70:
score: 0
Runtime Error
input:
26005 130000 1 2 17389 23170 22758 10732 22543 23408 19301 17389 25848 18936 18936 21025 22543 25892 22758 2303 770 18936 10696 4373 22850 4373 16352 4373 7382 17389 14837 4373 21654 4373 22513 22758 7977 22543 4373 17414 14556 18936 17389 21040 22543 21380 9862 22543 20597 4373 17389 10282 9182 437...
output:
Unauthorized output
result:
Subtask #6:
score: 0
Runtime Error
Test #82:
score: 31
Accepted
time: 10ms
memory: 5760kb
input:
10000 11000 1 3 242 6594 7153 1171 3833 5240 2223 8238 7347 5616 7332 7717 1485 7260 2323 3839 7359 9719 6973 7446 9821 1553 4652 663 3200 30 9465 9801 5461 4480 2298 513 5950 7473 4726 6408 7990 2674 4736 7663 9124 7932 1022 807 6870 6840 8507 62 4036 7781 1867 4826 9093 6486 9303 7974 5399 4503 90...
output:
Accepted: 38
result:
points 1.0
Test #83:
score: 31
Accepted
time: 17ms
memory: 5768kb
input:
10000 12000 2 3 4857 2452 4361 665 4690 1770 2293 1547 4473 1035 7838 4758 3370 7154 5965 4793 6751 7912 108 311 7994 7516 930 1881 3688 8582 8788 3182 9538 8770 3705 6854 1082 7659 3142 3131 1749 6271 6129 8039 7431 848 4893 206 8341 6642 1088 100 8427 6334 1946 6672 1221 501 1019 7308 7802 538 658...
output:
Accepted: 37
result:
points 1.0
Test #84:
score: 31
Accepted
time: 67ms
memory: 21584kb
input:
90000 101000 4 5 56091 53745 50551 69009 41341 69902 10324 82455 21704 16360 38034 86326 20751 84303 12519 5756 26410 49921 61625 87388 41276 27250 64383 64446 60811 69266 63192 35949 67415 4762 49420 53900 52643 74779 55133 85578 25210 63881 65649 42267 33905 13198 1353 72860 26338 81080 21165 7860...
output:
Accepted: 48
result:
points 1.0
Test #85:
score: 31
Accepted
time: 133ms
memory: 21932kb
input:
90000 105000 3 99 86503 23751 17425 85839 2827 42783 68907 30080 9311 44087 34334 16980 62285 50804 34671 25544 58671 73724 78917 86481 69381 36611 33743 44518 80626 1026 71227 75339 77255 36925 72285 38384 23232 15852 30552 36813 78564 53390 5032 9979 45179 43133 19536 17869 78481 76272 8052 50389 ...
output:
Accepted: 49
result:
points 1.0
Test #86:
score: 31
Accepted
time: 175ms
memory: 22000kb
input:
90000 110000 3 999 73530 26097 15598 49512 19727 2591 44549 68835 83814 37610 26854 23699 34946 22039 31851 70554 81204 72799 43004 16235 9657 58241 84910 45683 57949 20644 64023 60528 16622 63229 3705 86052 2665 70592 46261 70450 18172 65840 55300 80502 86781 30316 89894 23688 60142 285 77211 24461...
output:
Accepted: 49
result:
points 1.0
Test #87:
score: 31
Accepted
time: 133ms
memory: 23396kb
input:
90000 130000 4 111 86771 33394 68780 6781 47630 19590 38335 80190 30551 84588 13107 11858 17336 72950 68287 35327 1788 40577 34803 64419 29337 88444 33354 75479 25641 82542 37999 17902 7122 73725 74971 52218 43234 68889 88640 68809 63697 83358 87572 59823 56081 59311 65971 18204 71515 38052 28070 59...
output:
Accepted: 48
result:
points 1.0
Test #88:
score: 31
Accepted
time: 130ms
memory: 21360kb
input:
90000 101000 7573002 75878368 46648 38155 71367 6224 27929 77151 8358 45628 23234 66538 9800 22816 54769 57218 26883 71773 8326 79184 45648 77456 41168 12433 52653 766 73164 59043 24450 28514 18887 82103 83964 61359 84125 65179 8871 60833 56587 32516 14549 21648 34242 86851 70299 30944 51963 10588 8...
output:
Accepted: 35
result:
points 1.0
Test #89:
score: 31
Accepted
time: 114ms
memory: 21796kb
input:
90000 105000 7638537 75812831 69741 417 28159 43542 29693 15583 76468 49324 73012 68820 66940 88793 78282 77505 12682 86146 699 60478 78259 31759 88497 4361 80557 57918 84210 57937 80923 47259 24784 71460 34354 87012 57446 80594 406 88435 64356 72649 47179 9710 31766 20718 60865 18462 48374 39523 49...
output:
Accepted: 47
result:
points 1.0
Test #90:
score: 31
Accepted
time: 124ms
memory: 21956kb
input:
90000 110000 8228359 75747281 34819 443 86473 7773 72621 68673 70253 62005 49348 87750 16060 73587 53940 15781 8607 70604 9351 14296 14689 56999 59957 36697 41691 50724 54680 79573 87458 72928 75264 20740 7713 75602 43747 83489 46790 21112 78865 14850 10684 74960 4821 77161 48931 1022 62035 36859 54...
output:
Accepted: 48
result:
points 1.0
Test #91:
score: 31
Accepted
time: 131ms
memory: 23024kb
input:
90000 130000 1 3 68121 25307 1310 38917 12821 57526 23843 18404 52199 58819 72709 64995 83666 88294 50659 669 13377 32321 47684 84131 29837 23817 24240 48591 66096 74754 87243 18069 31385 25678 26538 23623 55934 62968 47063 9277 37300 21771 82547 86170 74316 87028 12188 28107 50431 28491 83994 83363...
output:
Accepted: 49
result:
points 1.0
Test #92:
score: 31
Accepted
time: 291ms
memory: 23108kb
input:
90000 130000 2 3 26702 10877 86423 32406 58706 6043 18472 46458 5067 28107 74464 24967 46685 83212 22758 1408 87091 60526 88737 72748 4833 24620 5485 58192 74512 81880 54084 23575 64359 76538 44832 53200 73473 69584 42242 81010 6795 80816 6146 79271 15547 71246 11584 69589 64973 76363 48869 29098 10...
output:
Accepted: 50
result:
points 1.0
Test #93:
score: 31
Accepted
time: 107ms
memory: 23192kb
input:
90000 130000 2 5 34986 9743 79304 29323 66236 68082 6019 34213 4073 47380 10584 24008 30024 15420 83928 27708 72502 63144 66586 8626 3381 81153 1 18210 4776 55807 16573 69850 54091 40931 64819 60781 48981 82204 15250 36794 26337 53852 12134 68037 15119 36712 65633 89543 84750 5543 43018 79242 15379 ...
output:
Accepted: 50
result:
points 1.0
Test #94:
score: 31
Accepted
time: 48ms
memory: 16568kb
input:
43336 129999 7966211 75485141 28523 28549 959 28523 28523 20436 28523 33883 28523 29267 12973 28549 28523 8195 37558 3122 14722 28523 32260 28549 7767 3122 19128 3122 18131 3122 19969 28523 3122 41170 3751 28549 19805 28523 9063 3122 18848 3122 28523 11694 3122 7893 33627 28523 28523 41765 28549 778...
output:
Accepted: 32
result:
points 1.0
Test #95:
score: 0
Runtime Error
input:
26005 130000 8031747 75419606 485 6122 20218 3858 12025 20218 19964 8426 22482 6547 2338 6122 9898 485 2202 6122 24612 20218 6547 2997 23884 6122 20218 1838 19284 485 20218 3358 13658 19964 3476 20218 6122 12994 6547 20576 25185 20218 6122 9647 21527 19964 21983 485 6547 1232 6547 13420 16974 6122 2...
output:
Unauthorized output