QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560109 | #8673. 最短路径 | forgotmyhandle | 100 ✓ | 3527ms | 248332kb | C++14 | 4.1kb | 2024-09-12 12:40:24 | 2024-09-12 12:40:24 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <random>
#include <tuple>
#include <queue>
#define int long long
using namespace std;
const int inf = 0x7ffffffffffffff;
vector<pair<int, int> > gs[200005];
vector<pair<int, int> > gt[200005];
int n, m, q, seed;
struct node {
int x, dis, cur;
};
bool operator<(node a, node b) { return a.dis > b.dis; }
int ds[200005], dt[200005];
int vs[200005], vt[200005];
vector<int> Ss, St;
priority_queue<node> qs, qt;
int Query(int s, int t) {
if (s == t)
return 0;
if (gs[s].empty() || gt[t].empty())
return -1;
int z = -1;
ds[s] = dt[t] = 0;
vs[s] = vt[t] = 1;
Ss.emplace_back(s);
St.emplace_back(t);
while (!qs.empty()) qs.pop();
while (!qt.empty()) qt.pop();
qs.push((node) { s, gs[s][0].second, 0 });
qt.push((node) { t, gt[t][0].second, 0 });
while (!qs.empty() && !qt.empty()) {
if (qs.size() <= qt.size()) {
node tmp = qs.top();
qs.pop();
int x = tmp.x;
for (int i = tmp.cur + 1; i < (int)gs[x].size(); i++) {
if (!vs[gs[x][i].first]) {
qs.push((node) { x, ds[x] + gs[x][i].second, i });
break;
}
}
int v = gs[x][tmp.cur].first;
if (vs[v])
continue;
vs[v] = 1, ds[v] = tmp.dis;
Ss.emplace_back(v);
if (vt[v]) {
z = v;
break;
}
if (gs[v].size())
qs.push((node) { v, ds[v] + gs[v][0].second, 0 });
} else {
node tmp = qt.top();
qt.pop();
int x = tmp.x;
for (int i = tmp.cur + 1; i < (int)gt[x].size(); i++) {
if (!vt[gt[x][i].first]) {
qt.push((node) { x, dt[x] + gt[x][i].second, i });
break;
}
}
int v = gt[x][tmp.cur].first;
if (vt[v])
continue;
vt[v] = 1, dt[v] = tmp.dis;
St.emplace_back(v);
if (vs[v]) {
z = v;
break;
}
if (gt[v].size())
qt.push((node) { v, dt[v] + gt[v][0].second, 0 });
}
}
if (z == -1) {
for (auto v : Ss) vs[v] = 0;
for (auto v : St) vt[v] = 0;
Ss.clear(), St.clear();
return -1;
}
int ans = ds[z] + dt[z];
for (auto v : Ss) {
int lim = (ds[z] - ds[v]) << 1;
for (auto e : gs[v]) {
if (e.second >= lim)
break;
if (vt[e.first])
ans = min(ans, ds[v] + dt[e.first] + e.second);
}
}
for (auto v : St) {
int lim = (dt[z] - dt[v]) << 1;
for (auto e : gt[v]) {
if (e.second >= lim)
break;
if (vs[e.first])
ans = min(ans, dt[v] + ds[e.first] + e.second);
}
}
for (auto v : Ss) vs[v] = 0;
for (auto v : St) vt[v] = 0;
Ss.clear(), St.clear();
return ans;
}
signed main() {
cin >> n >> m >> q >> seed;
mt19937 gen(seed);
vector<tuple<int, int, long long>> edges(m);
unsigned max = -1u / n * n;
auto sample = [&]() {
unsigned x;
do { x = gen(); } while(x >= max);
return x % n + 1;
};
for(auto & [u, v, w] : edges) {
u = sample();
v = sample();
w = gen();
gs[u].emplace_back(make_pair(v, w));
gt[v].emplace_back(make_pair(u, w));
// cout << u << " " << v << " " << w << " asdf\n";
}
for (int i = 1; i <= n; i++) {
sort(gs[i].begin(), gs[i].end(), [](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });
sort(gt[i].begin(), gt[i].end(), [](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });
}
while (q--) {
int s, t;
cin >> s >> t;
cout << Query(s, t) << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 18008kb
input:
4 8 5 1112792816 2 3 4 3 4 3 3 2 1 4
output:
3419197189 1798364963 1798364963 3986398077 2337967903
result:
ok 5 lines
Test #2:
score: 5
Accepted
time: 3ms
memory: 18856kb
input:
2000 2000 2000 3336994405 659 1650 1678 341 818 235 1380 1865 1927 1366 1233 1673 267 1698 775 1022 1255 1110 1533 1928 1854 169 1579 729 449 1335 943 583 360 50 795 926 1584 911 1924 604 280 309 1429 420 1107 1858 1466 76 265 1109 1077 622 245 1941 957 1434 1560 1128 122 51 229 925 826 1006 851 323...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 2000 lines
Test #3:
score: 5
Accepted
time: 7ms
memory: 18488kb
input:
1000 2000 2000 1526732796 400 914 837 927 7 271 873 60 934 156 981 329 973 512 276 54 540 278 605 230 681 555 636 706 955 618 640 214 859 696 267 595 38 839 309 12 484 919 746 49 948 337 607 638 438 163 817 869 95 518 534 376 369 331 665 64 736 970 154 41 510 425 876 907 143 803 270 403 350 286 131 ...
output:
14198403396 -1 20203456441 11552404306 16160464812 27144556597 -1 5570702410 -1 19513776618 10597134504 8945453029 20326028889 -1 12608727274 17050357023 -1 -1 15134668738 19589312812 32078322699 16255615559 -1 20150114514 15485138820 -1 5265380455 -1 19291857101 -1 -1 -1 19427108277 17619903738 -1 ...
result:
ok 2000 lines
Test #4:
score: 5
Accepted
time: 7ms
memory: 17900kb
input:
500 2000 2000 3177778089 135 446 384 405 132 455 458 142 271 60 354 277 145 378 374 34 394 307 487 141 327 34 367 265 310 337 116 307 50 279 247 8 151 3 386 17 500 139 2 389 184 217 454 490 296 421 318 180 163 369 4 324 344 268 495 190 268 496 431 84 45 328 50 81 176 390 234 36 293 182 416 486 46 27...
output:
5092376329 9080104016 9223230484 6790695535 1911804904 5716235553 8583960391 5016988950 5289686236 2389749962 6844313639 7113134103 7814059833 12150667601 7933731395 4058410466 4907384372 3338886350 10009203917 5364419601 2895425798 9616179679 7137622338 5200372729 2862982942 6332664702 4507301136 3...
result:
ok 2000 lines
Test #5:
score: 5
Accepted
time: 0ms
memory: 13964kb
input:
1 2000 2000 1058024304 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 2000 lines
Subtask #2:
score: 15
Accepted
Test #6:
score: 15
Accepted
time: 527ms
memory: 211324kb
input:
3000 3000000 10000 37461678 2873 1368 1757 2000 1262 1822 2484 1778 2055 2096 2545 366 2923 2028 1469 1874 691 631 1173 2967 894 2020 1207 881 373 236 1913 1923 1351 16 1066 2032 471 1561 1047 2043 457 145 2728 1752 2521 1199 1568 904 2515 543 1472 2161 748 2744 748 1908 912 172 2340 2494 977 267 10...
output:
36084543 49860181 45803385 27805775 41392651 43506617 39517515 39687913 37675345 23367579 37276839 32364058 50703016 26615083 25983590 51209814 42921191 31222991 39092809 25257238 36267824 60108033 34199475 45804995 35826034 34257048 38718065 55135658 31005342 41408425 35033769 37667712 42873640 378...
result:
ok 10000 lines
Test #7:
score: 15
Accepted
time: 389ms
memory: 163432kb
input:
3000 2000000 10000 2522167365 2102 2825 724 1689 2259 2561 1681 677 62 2183 2589 1214 926 1138 674 2610 1679 1607 1349 2461 2617 1599 457 2347 584 518 1506 554 2954 470 1027 893 1924 2 2624 2746 1366 2651 2236 2085 362 2871 1413 1763 2497 404 1507 1216 894 322 2221 2553 824 2374 1883 1507 2484 2504 ...
output:
65574243 49955828 53828505 51865209 52351116 61557386 51116830 55590246 56377606 32235042 40593621 48849551 65887052 65047947 68965925 45241121 29819326 68037564 51238828 51815122 51454820 50482802 78004899 69718038 51304835 72570590 63002470 71137709 72879314 39737181 46218127 56704281 46947435 745...
result:
ok 10000 lines
Test #8:
score: 15
Accepted
time: 278ms
memory: 94300kb
input:
3000 1000000 10000 711905757 844 1281 882 1379 1448 2597 2686 1871 1556 677 337 871 825 248 1686 345 1259 775 422 763 2445 2585 1514 1028 90 1993 2203 2185 2965 2115 499 2266 2274 2635 713 450 2978 1453 1745 1010 11 350 1746 2622 1070 1458 438 1462 2936 2707 1797 2495 1929 873 1426 32 1696 548 2756 ...
output:
137380549 162704262 143745916 115032641 79062560 136541282 75207874 55127915 100171107 113209549 114113337 128511651 121886243 151535892 106186341 124611628 123504840 127411130 157283803 92948750 154286595 124377360 88897895 191915816 111939138 111074921 99047774 95249923 136436236 57049943 93591345...
result:
ok 10000 lines
Test #9:
score: 15
Accepted
time: 193ms
memory: 55188kb
input:
3000 500000 10000 4065069523 1355 22 595 1315 137 828 444 1241 483 1807 1852 377 1292 2452 478 1758 2712 2071 2243 1344 194 2765 2645 1718 2078 202 1860 2607 495 1091 2492 2800 2594 694 2021 2441 1393 1253 1378 2008 114 727 1019 196 1142 71 2787 2507 650 2675 2074 2132 2697 614 1611 1662 2687 358 13...
output:
283099212 197991417 240849607 272997490 378109456 160014053 252448699 281163198 280701476 178120202 189979017 272229633 267521047 219833816 183204444 275985942 208578258 148366474 287620336 264106800 220537155 167544642 306771926 200838815 179562301 313150724 246238367 194938277 197389047 201592436 ...
result:
ok 10000 lines
Test #10:
score: 15
Accepted
time: 159ms
memory: 25128kb
input:
3000 100000 10000 2346395888 2334 174 757 2882 2571 2749 2571 1300 1511 2435 170 1648 107 465 2588 2135 1571 1754 2919 2295 717 129 1779 2941 1493 1505 1784 470 164 371 1381 1204 1644 1556 2234 1583 54 2836 815 777 1060 671 1147 1945 879 2968 2030 609 770 2226 2414 1944 1893 885 478 1705 643 439 135...
output:
1037539058 841259924 1119227208 936606501 1124792817 550785284 1187414290 1105329599 534927835 1079864539 1056661616 1426806296 1387193176 717428828 1083183267 793850415 455433261 527722167 1087705276 1140313309 1048197735 777649783 1066670304 1244984113 1535939812 1008629859 1033454877 1242231980 1...
result:
ok 10000 lines
Test #11:
score: 15
Accepted
time: 0ms
memory: 18720kb
input:
3000 3000 10000 397949456 418 2179 1809 996 1420 2230 204 2974 2416 2274 2601 2425 172 1604 263 2652 2446 2508 1807 1321 1619 2575 1918 735 201 2718 134 1960 2804 22 189 988 1949 39 2260 2933 22 1853 2721 761 911 2218 2189 1676 2461 2594 471 643 1645 1453 144 1601 2501 1592 53 1710 1452 596 352 2347...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 10000 lines
Test #12:
score: 15
Accepted
time: 7ms
memory: 14360kb
input:
3000 1 10000 1332094416 2358 1322 1311 2414 1442 253 388 2803 2125 2362 762 2919 1027 1814 2431 1544 671 519 2498 1960 2056 729 857 2962 1502 1137 920 658 1745 100 2185 154 1963 2865 2967 1982 1041 171 2578 761 2965 816 1246 1765 1175 1028 2115 192 783 1447 494 1985 2181 427 1759 2895 2066 2047 674 ...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 10000 lines
Subtask #3:
score: 10
Accepted
Test #13:
score: 10
Accepted
time: 54ms
memory: 34272kb
input:
200000 200000 10000 1824322211 104482 112162 130667 13436 36792 142259 51832 97549 15358 180076 128251 92635 45296 195115 62109 38014 22014 86754 79735 103777 94797 96086 196760 5955 45622 59618 12995 62585 55686 156402 23085 68138 170749 148553 97603 160274 112975 22651 116322 190720 84774 57075 23...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 10000 lines
Test #14:
score: 10
Accepted
time: 23ms
memory: 26852kb
input:
200000 100000 10000 1394653802 99794 128174 196511 141958 176353 6707 19037 95308 12331 132159 47825 12373 47277 130874 165656 114428 81800 12371 165878 128160 33280 71225 139344 138789 126396 182051 103407 151857 20873 18698 155652 38063 150807 191146 57310 174863 114490 88197 158133 29636 137962 1...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 10000 lines
Test #15:
score: 10
Accepted
time: 18ms
memory: 26488kb
input:
100000 100000 10000 913053279 28316 35031 36768 9164 74111 12192 71120 23394 97477 34141 50880 24433 99500 23365 99785 571 95784 50853 8313 70744 33410 27807 29073 96498 82964 79943 32999 84423 90798 98756 98245 89258 89589 49557 90152 40866 53406 41385 33889 39018 42199 52421 13784 26639 85311 5769...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 10000 lines
Test #16:
score: 10
Accepted
time: 4ms
memory: 13356kb
input:
1 1 10000 1920830832 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 10000 lines
Subtask #4:
score: 20
Accepted
Test #17:
score: 20
Accepted
time: 1817ms
memory: 56724kb
input:
200000 500000 10000 3113327438 68816 31422 174349 125983 18111 188786 84806 87249 142007 180723 95611 116398 104758 196349 77547 89859 120350 77199 110906 10209 177461 194861 115505 105566 27493 166237 15676 158290 86204 116010 159979 125659 132461 61989 194289 157721 18830 82910 166696 98162 125208...
output:
21671419385 -1 31996366393 19295613250 -1 25762674206 -1 -1 30333017011 19365143518 -1 -1 33507263304 23396138679 19478702596 -1 -1 -1 20149023019 23727970709 24229890807 28875639856 -1 22877254445 25605430611 27724721382 -1 26550979061 25161604327 -1 22676819628 19348763468 -1 24220635647 161988758...
result:
ok 10000 lines
Test #18:
score: 20
Accepted
time: 1609ms
memory: 52988kb
input:
200000 450000 10000 1118169521 166796 113456 137783 155607 193135 111481 191025 126327 140709 98310 71232 162805 123178 64110 544 17147 106458 55180 150000 180727 139960 179775 18164 170136 111083 82218 52373 192981 139451 45685 109599 150246 95384 192714 26113 50377 150612 140121 106385 49534 19376...
output:
-1 40341861981 28261869830 30941339003 -1 30242356622 25947373832 35789130178 20024577904 30800614840 -1 -1 -1 22653608122 -1 21988625756 28969753407 25170387977 24360874041 36856287014 22511857899 -1 30515753641 28085041550 28476706709 21458298709 17897166454 24380647293 31979536077 -1 -1 -1 230416...
result:
ok 10000 lines
Test #19:
score: 20
Accepted
time: 1386ms
memory: 49244kb
input:
200000 400000 10000 2683659029 72640 80138 7490 54505 190375 29042 52012 93520 180196 75910 47888 44648 106740 132108 189606 166273 37032 2816 197049 100001 115943 170000 1193 5696 108267 88671 73385 182154 84096 121410 92545 95584 112520 71878 153997 172311 20345 148456 8508 145591 178397 72859 171...
output:
-1 25105637352 -1 -1 34928861348 31515217563 31869465750 -1 -1 22588826239 -1 31737680614 28892362640 -1 -1 30572530270 31628793370 23013498514 32904666194 -1 29089481648 -1 33305918084 -1 -1 -1 -1 32444724628 33336417682 -1 33245699259 25265532583 35802755133 21946108912 31424462722 35294293316 290...
result:
ok 10000 lines
Test #20:
score: 20
Accepted
time: 1006ms
memory: 37048kb
input:
100000 250000 10000 4072199476 61751 52336 77024 47153 70014 54375 42928 25738 28313 47562 87355 47044 70852 19607 74472 7735 5423 20704 64721 37486 84352 86635 60357 60808 5006 26865 97382 71386 5159 26143 17324 49804 26987 3608 78369 80151 92558 91696 89955 36749 4378 25842 10918 23185 92107 28060...
output:
24216761778 20150295081 -1 -1 22753387125 -1 29982588593 18036093297 29157832497 -1 26535394899 13028717125 20654367444 -1 15252230332 -1 18048554280 25487435955 19722901875 21112098238 23099559236 19581393944 -1 -1 22230187683 20655957586 19357021503 32071590351 19563625516 15831428235 29054032276 ...
result:
ok 10000 lines
Subtask #5:
score: 20
Accepted
Test #21:
score: 20
Accepted
time: 1816ms
memory: 56864kb
input:
200000 500000 10000 1843053063 3409 108359 168924 184622 13119 119837 109492 38050 97152 51201 49047 12472 183998 191613 193074 177289 194248 104409 15509 88499 61967 143398 4532 56790 196650 158711 63655 70744 140178 107299 63530 87330 127334 159237 7134 184418 125289 28604 176966 179527 181695 128...
output:
18098332289 22666064981 23549058925 26339412859 -1 23116762056 22209493371 21117534178 22029252897 33952599088 17793204212 13278636159 25843769632 18134229421 29623865096 23847021502 20878297870 -1 -1 21042457357 23208160613 19615484227 26566774108 15726744387 23457868594 23352911380 16578768343 242...
result:
ok 10000 lines
Test #22:
score: 20
Accepted
time: 1876ms
memory: 56356kb
input:
150000 500000 10000 1171171831 91544 80638 88533 64906 57189 104784 102394 38679 38414 49143 137564 139395 140558 140970 64039 53145 108163 56995 38924 95572 48927 4259 148782 85367 44887 19484 36838 83718 10792 128933 90704 81675 116605 19578 51500 21602 137498 101466 7037 146764 116437 62263 46477...
output:
14685453949 13815636857 -1 17273133560 17081019981 7904131229 14150324359 -1 13935305592 15172554384 17847228590 18396095342 18099059942 14018081826 13538417865 13039858691 -1 11955929164 19405668785 16207189818 16205956113 13534856652 19625612871 18222174103 11952110215 18451844738 11569289868 1110...
result:
ok 10000 lines
Test #23:
score: 20
Accepted
time: 1586ms
memory: 56576kb
input:
100000 500000 10000 2631726914 31929 27879 6094 25893 24382 94271 36889 15335 70257 50001 55562 28458 89684 21544 11675 76002 1629 82978 61853 95897 1782 75635 5235 30571 84060 72640 12564 23560 56129 28773 94060 9558 38539 63504 35643 99532 25042 68803 42452 40248 72549 51285 86656 88890 70470 5809...
output:
15132037824 8408831601 9425277425 11014294681 8087246201 10199187203 9267001014 12221174318 10266262545 7046786930 10643941494 7901306948 9433569044 8856408603 8459463884 8354267819 10803653357 11313030123 8895533910 10084321258 9070006233 10214822733 12149015809 9798158858 10769868779 9310675329 11...
result:
ok 10000 lines
Subtask #6:
score: 10
Accepted
Test #24:
score: 10
Accepted
time: 2425ms
memory: 244320kb
input:
100000 3000000 10000 3892765041 14843 34156 43390 49542 38564 95501 26194 87126 18638 53346 69414 47011 95472 58303 44370 77172 75652 90555 94386 31888 47911 9905 70599 97061 52764 24896 31445 15589 82314 43852 97155 93412 11834 45082 75614 42459 67802 32024 82389 4968 32860 62514 97630 28012 14839 ...
output:
1547972368 1533240012 1192488694 1802115335 1491444021 1888896300 1720188008 1762089620 1815841406 1831208977 1250925907 1756812381 2027344758 1385409721 1937527554 1877583272 1632784703 2090242303 1694524102 1818975564 1429598050 1599437722 2286394605 1416358110 1929044811 2022891575 1487757623 156...
result:
ok 10000 lines
Test #25:
score: 10
Accepted
time: 2033ms
memory: 168940kb
input:
100000 2000000 10000 2082503433 58880 78421 14548 46231 99049 88344 22391 26025 25236 34840 77162 82668 5667 67117 12870 11907 49640 62723 1755 5382 21226 76188 59145 70335 4679 71179 32038 73516 72621 41497 49627 18273 40479 91715 73191 40867 26710 98234 99898 23597 48509 24994 15771 1679 11605 571...
output:
2550292014 2088525319 2688949421 2128205012 3265691684 2456734516 1642691812 2983165881 3021975646 3122679543 2170817246 3179344726 2692378689 2567981687 2298179789 2073907330 2763664628 1855487724 2293201092 2937148401 3601836798 3010987679 3688384387 2780648332 2363790153 2058109458 2361104139 370...
result:
ok 10000 lines
Test #26:
score: 10
Accepted
time: 1737ms
memory: 93376kb
input:
100000 1000000 10000 272241824 59814 46877 53003 67113 92238 72676 61692 32219 21435 50927 52205 42516 15862 43227 81371 46643 23628 77996 17636 78876 35758 42470 56202 76312 91185 74357 8439 64147 30223 82246 36692 51645 77637 81452 11984 6570 85619 99036 17407 42226 88351 11665 66616 99537 49586 7...
output:
6418345560 3595930024 6543274734 5474244226 4520275434 5150335953 4277692210 5986379098 4573937177 7984631087 5980452817 4449908880 5275131238 6897728511 5018007685 6108102390 5945939138 5849450340 3278653602 6392948014 4711245030 5196851535 5369208668 4949967489 4687794608 6120501385 5234779104 587...
result:
ok 10000 lines
Test #27:
score: 10
Accepted
time: 1621ms
memory: 78580kb
input:
100000 800000 10000 3920732141 4775 79843 49776 38439 38404 40798 12968 37738 29610 93752 55625 52220 16442 22778 27113 62439 99965 97616 3424 91930 51742 74410 23980 5990 57419 46555 82541 53857 52056 64189 30953 99783 76059 44236 32329 96980 63601 4870 1338 56203 12984 58609 1614 22674 85619 39445...
output:
6773118428 6016808197 5294603101 5431630355 6719722231 6061433622 8321347545 7106574205 4706280676 7514388136 7884070358 6290598631 5771030241 5766485204 5797476763 7907803690 4874071175 5172901782 5331218426 6303917257 6547572351 7979709668 5122570551 7117262205 6018533347 6498260413 6167971007 841...
result:
ok 10000 lines
Test #28:
score: 10
Accepted
time: 1575ms
memory: 63892kb
input:
100000 600000 10000 3061395323 36617 79163 81465 62779 84821 54014 12788 41768 64772 30622 3284 67504 87702 85785 99616 91076 84947 48850 75710 6105 96004 496 19547 30441 27479 50207 30663 34289 90942 66477 28790 39633 58480 53614 75936 17647 90823 3257 9153 1332 19361 75529 77274 41549 59392 1342 1...
output:
9835743721 7039924613 8756250230 8114338602 7567988827 10002241606 5394748574 9287511700 8239115800 8935383817 9412797324 6530025953 8157825053 7660789241 7019764161 9302410827 6356033267 8636641495 10127260445 8322147834 8000414596 5875569246 7693550693 10961604471 9316446730 8294729535 10243692052...
result:
ok 10000 lines
Test #29:
score: 10
Accepted
time: 1555ms
memory: 56008kb
input:
100000 500000 10000 3179262801 67161 72808 68834 15085 42796 47728 4873 66300 66430 11153 28402 64694 76489 49933 79217 34377 27 55356 58092 54036 42741 33128 94944 13358 94541 64111 96221 73373 52940 41380 47429 36512 85745 24783 73137 90630 45773 4360 19052 59573 68581 76287 12822 67716 28403 6655...
output:
10188155725 9209437821 8847315889 11011468478 8788835022 8986785829 10236420159 13913246671 11067547259 8093347691 18118968255 6896779657 8009481872 -1 12800453640 12331519198 11970880045 10027338198 9259060846 7402033273 12435316483 9062839441 12567341116 12724670568 12909916102 11827258505 1225136...
result:
ok 10000 lines
Test #30:
score: 10
Accepted
time: 1221ms
memory: 41600kb
input:
100000 300000 10000 1772390096 63771 3007 37783 50232 70799 98975 4005 19364 5419 29975 3221 76445 28240 84550 51474 71935 19315 66916 1435 99673 46044 1721 802 96238 45608 43587 60685 3992 51912 63765 408 82112 64064 40178 46545 20199 84968 67190 26075 93889 3118 68205 38124 7765 44243 19994 34606 ...
output:
-1 19386480063 15721305709 17164757039 17714916448 -1 20652203356 19106483574 11009499296 20046689082 20551451248 -1 17170657439 18149216493 24245343288 16267945234 15793492376 15736434173 15475180103 23485577894 18461014260 22244038766 19128982293 12717186821 12609248210 26956793470 19312166564 201...
result:
ok 10000 lines
Test #31:
score: 10
Accepted
time: 148ms
memory: 27964kb
input:
100000 120000 10000 3722831312 3597 90060 24046 23742 23836 50006 93945 87896 52383 98640 53299 65833 3995 94463 39053 98162 2121 35581 20872 90599 10613 31448 20700 35087 71009 41522 83538 40133 9536 93951 27146 92826 31355 83754 53782 4496 89296 90864 99581 71296 72237 5443 64633 57653 81081 57544...
output:
83052283628 92762223236 -1 -1 -1 -1 44797640067 -1 -1 -1 -1 111377024036 -1 74215424419 -1 -1 112926898612 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 124912853776 -1 -1 -1 108529420155 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 16107731465...
result:
ok 10000 lines
Test #32:
score: 10
Accepted
time: 3ms
memory: 13096kb
input:
100000 500 10000 32306511 23546 46114 64323 84318 92663 39412 53318 87811 78360 32702 88882 63307 5048 97070 44915 93158 35476 87671 35288 93192 24620 54606 11251 22826 11526 16718 76828 11718 99115 11029 48846 27710 54568 14693 53033 501 40655 98500 28302 38260 25907 49212 37638 3879 2223 58172 772...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 10000 lines
Subtask #7:
score: 20
Accepted
Test #33:
score: 20
Accepted
time: 3527ms
memory: 248332kb
input:
200000 3000000 10000 3910662331 161257 40967 50546 86049 199665 199302 177403 36274 158790 143151 193304 78511 28032 149723 96394 37099 2157 76024 195400 34830 41933 147591 191613 96468 194837 67293 57992 63117 24749 6694 117818 87323 46130 53470 174812 24950 149173 124886 119910 54123 2297 124533 5...
output:
3371897180 3059012504 3899803743 4918664465 3834117056 3101758258 4211432244 3700678845 3320322266 4020388668 3314213999 4156507838 3045843635 3379778417 3201003504 4511026914 4847106102 3502897631 3579081638 3470448652 4322207527 2160161436 4372954162 3841655899 3367608876 3864513044 4225021719 377...
result:
ok 10000 lines
Test #34:
score: 20
Accepted
time: 3352ms
memory: 168728kb
input:
200000 2000000 10000 2100400722 62191 109424 121705 6930 25558 16338 40896 18277 89580 91941 101052 38359 70931 193129 64894 4539 176145 124000 35472 141029 47953 56977 55967 69742 181344 13576 134393 21044 147760 104339 94483 20695 74776 75910 72389 23358 8081 158392 137419 172752 142139 187012 461...
output:
6283629982 4810712484 6173371551 5572267087 4533360250 6948138461 3763810206 6015991679 5138843815 5882103239 4651947070 5141390603 6054389311 7266250132 4406869907 5633307251 4787973112 5399509441 5723882182 4777557240 6651824180 3628172060 5633580623 7288229990 6224865765 6453345185 5384740659 464...
result:
ok 10000 lines
Test #35:
score: 20
Accepted
time: 2978ms
memory: 94096kb
input:
200000 1000000 10000 290139113 138932 153688 168671 103620 18747 33374 112901 24472 85778 40732 176095 174016 56934 101943 66099 106570 117429 196168 75545 14523 29780 55964 177216 75719 176362 159858 2281 11675 29555 177792 46955 145556 46525 122543 145774 189061 66990 159194 154928 91381 25084 494...
output:
8399082592 11942156772 10632368824 7965114443 10726017478 10973870332 9600481203 10610255848 12075078315 10893634624 11983620763 10634804855 10777627700 13288195275 7038962823 8587722108 15407301616 10762596023 9955242588 11706886347 9380360663 11405062382 9230394518 9850418344 11154477114 710020190...
result:
ok 10000 lines
Test #36:
score: 20
Accepted
time: 2891ms
memory: 79320kb
input:
200000 800000 10000 107365368 8958 40282 9520 38530 7942 11121 60885 118165 109872 124474 152570 115969 164220 62991 125688 76296 10174 59133 85181 149346 51612 93636 34250 115577 9363 48664 152949 21291 149427 18723 31464 40076 94174 110017 66784 155169 124685 118978 192878 46821 165643 104427 7756...
output:
16101581913 14814516851 13447309080 13922492557 12974523216 17116873103 10101346227 16823516981 14476914783 12468824487 15167111568 12895759329 15237942483 13265802110 13803894941 16722995588 17428015165 11820577484 14636717323 11438920462 13338846632 10494137075 13894988519 13440904283 11789212099 ...
result:
ok 10000 lines
Test #37:
score: 20
Accepted
time: 2442ms
memory: 64264kb
input:
200000 600000 10000 3542995846 8095 72306 108505 30165 111255 115825 84897 89490 145034 28640 229 163956 135480 69102 141295 37637 195155 143071 24763 153122 95874 52426 5625 148540 170911 52315 125263 101723 121017 53715 162004 147222 119699 186691 10390 175836 184611 17365 100693 91950 72020 88643...
output:
-1 17621313448 -1 16371547841 20066994265 18765965574 19301473260 -1 19157184868 22874209263 21481207158 18347730067 19733170516 21665328373 19624461296 17186647628 18217491314 19202137618 21488541303 21009045091 23122892299 22462424446 20058429107 16986340223 20789045175 -1 20411079578 17324148963 ...
result:
ok 10000 lines
Test #38:
score: 20
Accepted
time: 793ms
memory: 41872kb
input:
200000 300000 10000 2253990620 67953 96150 40630 150322 97232 102002 51922 91279 177169 27993 166 164386 76018 35164 125858 185792 129523 128433 193592 13985 189018 120947 143776 105826 189041 2592 155286 38722 81987 151002 57815 98213 125282 138663 105192 178388 46052 157106 50319 151803 31585 1813...
output:
-1 -1 -1 26660131132 -1 46293005611 -1 -1 48805837848 48395550809 -1 46948511504 -1 46081117220 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 39125183301 -1 -1 -1 45247672254 44390888387 87346128791 63163418734 54831836614 73653972200 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 49649002719 -1 -1 -1 52144062577 564698...
result:
ok 10000 lines
Test #39:
score: 20
Accepted
time: 404ms
memory: 38020kb
input:
200000 250000 10000 258832703 198637 112776 36768 147243 39552 191994 190845 97652 175871 178284 151596 10793 94438 127116 48855 178488 91440 139117 56878 127606 151518 105861 46435 170396 48439 85869 167791 73412 102530 80676 7435 57392 88205 69389 137016 38340 153642 71212 14199 70471 124333 71660...
output:
116524522245 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 48618048834 -1 -1 63037831419 -1 -1 -1 -1 -1 -1 -1 -1 94402656798 -1 -1 -1 -1 69818576979 -1 -1 -1 68274847440 -1 -1 -1 -1 -1 -1 -1 103267319139 -1 -1 112520370452 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 920298166...
result:
ok 10000 lines
Test #40:
score: 20
Accepted
time: 60ms
memory: 33384kb
input:
200000 190000 10000 1153753065 9920 14655 52978 191130 135457 140582 146804 223 148065 59366 76008 156435 72706 5072 47962 82788 44988 34190 168139 138196 187512 96794 148080 164727 113814 21061 150770 17208 113704 157553 197804 34452 8693 37271 23984 61277 59639 154627 154690 30840 78813 77650 6524...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 10000 lines
Test #41:
score: 20
Accepted
time: 6ms
memory: 14720kb
input:
200000 500 10000 225477577 79282 74956 34929 91129 175627 43215 71315 115805 62274 24954 153226 44601 96234 20058 42883 119170 163308 71790 161793 11365 158338 166061 172569 103615 141052 73021 53493 21411 25662 58557 148178 190552 32128 108604 187329 108889 139853 180991 85481 198419 63428 98367 13...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 10000 lines