QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#469572 | #943. Dynamic Diameter | zzy0922 | 49 | 163ms | 38060kb | C++14 | 3.8kb | 2024-07-09 20:17:54 | 2024-07-09 20:17:54 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
inline void chkmax(i64 &x, i64 v) {
x = std::max(x, v);
}
constexpr int N = 100005;
struct cluster {
int u, v;
i64 f[4];
};
cluster comp(const cluster& a, const cluster& b) {
cluster c;
c.u = a.u;
c.v = b.v;
c.f[0] = std::max({a.f[0], b.f[0], a.f[2] + b.f[1]});
c.f[1] = std::max(a.f[1], a.f[3] + b.f[1]);
c.f[2] = std::max(b.f[2], b.f[3] + a.f[2]);
c.f[3] = a.f[3] + b.f[3];
return c;
}
cluster rake(const cluster& a, const cluster& b) {
cluster c;
c.u = a.u;
c.v = a.v;
c.f[0] = std::max({a.f[0], b.f[0], a.f[1] + b.f[1]});
c.f[1] = std::max(a.f[1], b.f[1]);
c.f[2] = std::max(a.f[2], a.f[3] + b.f[1]);
c.f[3] = a.f[3];
return c;
}
struct node {
int tp, ls, rs, fa, sz;
cluster vl;
node() : tp(-1), ls(0), rs(0), fa(0), sz(1) {}
}ttree[N << 1];
#define tp(p) ttree[p].tp
#define ls(p) ttree[p].ls
#define rs(p) ttree[p].rs
#define fa(p) ttree[p].fa
#define sz(p) ttree[p].sz
#define vl(p) ttree[p].vl
inline void pushup(int p) {
// assert(~tp(p));
if (tp(p))
vl(p) = comp(vl(ls(p)), vl(rs(p)));
else
vl(p) = rake(vl(ls(p)), vl(rs(p)));
}
int n, q, W, tot;
std::vector<int> t[N];
int siz[N], son[N], dep[N], fa[N];
void dfs(int u) {
siz[u] = 1;
for (int v : t[u]) {
if (v == fa[u])
continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs(v);
siz[u] += siz[v];
if (siz[v] > siz[son[u]])
son[u] = v;
}
}
int merge(std::vector<int> cid, int type) {
if (cid.size() == 1u)
return *cid.begin();
int sum = 0, csum = 0;
for (const int i : cid)
sum += sz(i);
csum = sz(cid[0]);
auto mid = std::next(cid.begin());
while (csum + sz(*mid) <= (sum >> 1))
csum += sz(*mid++);
int cur = ++tot;
tp(cur) = type;
fa(ls(cur) = merge(std::vector<int>(cid.begin(), mid), type)) = cur;
fa(rs(cur) = merge(std::vector<int>(mid, cid.end()), type)) = cur;
pushup(cur);
return cur;
}
int _build(int u, int utp, std::vector<int> &vec) {
if (!son[u]) return u;
std::vector<int> cid;
cid.push_back(son[u]);
for (const int &v : t[u]) {
if (v == fa[u] || v == son[u])
continue;
std::vector<int> tmp;
tmp.push_back(v);
cid.push_back(_build(v, v, tmp));
}
vec.push_back(merge(cid, 0));
if (son[u]) _build(son[u], utp, vec);
if (u == utp)
return merge(vec, 1);
return 0;
}
int rt;
inline void build(int tree_rt) {
dfs(tree_rt);
std::vector<int> tmp;
tot = n;
rt = _build(tree_rt, tree_rt, tmp);
}
void update(int x) {
assert(x <= tot);
if (x != rt) {
assert(x);
pushup(fa(x)), update(fa(x));
}
}
std::map<std::pair<int, int>, int> id;
int tid[N];
i64 w[N];
int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> n >> q >> W;
for (int i = 1, u, v; i <= n - 1; i++) {
std::cin >> u >> v >> w[i];
id[{u, v}] = id[{v, u}] = i;
t[u].push_back(v), t[v].push_back(u);
}
build(1);
assert(!fa(rt));
// out(rt);
for (int i = 2; i <= n; i++) {
tid[id[{i, fa[i]}]] = i;
std::fill(vl(i).f, vl(i).f + 4, w[id[{i, fa[i]}]]);
update(i);
}
// std::cout << vl(rt).f[0] << '\n';
int d;
i64 las = 0, e;
while (q--) {
std::cin >> d >> e;
d = (las + d) % (n - 1) + 1;
e = (las + e) % W;
d = tid[d];
assert(d);
std::fill(vl(d).f, vl(d).f + 4, e);
update(d);
std::cout << (las = vl(rt).f[0]) << '\n';
}
}
详细
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 0ms
memory: 19428kb
input:
10 100 10000 3 4 115 4 7 2757 1 5 5809 8 5 1111 6 2 7043 6 5 4932 6 4 4171 9 5 8499 10 5 2395 1 3517 8 7196 1 8064 6 7437 6 2421 8 67 7 6695 3 1217 1 920 1 1786 4 2541 5 266 4 6167 0 7590 6 195 8 4087 2 8073 6 8065 5 2882 2 3292 4 3435 6 8447 8 3419 0 9545 1 7922 0 4088 8 2546 4 7071 1 722 6 9178 0 ...
output:
21119 21746 23057 18619 18309 18309 19479 18309 19533 18309 18186 18262 19939 21768 20410 22382 20410 21356 17833 17119 13244 7187 4529 6469 8465 8524 9139 10958 11513 9377 9567 8338 8034 5923 5027 2900 2285 2068 1882 1945 2775 4745 4710 5813 7516 5813 4710 5561 6651 8019 9192 9658 8822 7818 5647 53...
result:
ok 100 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 19960kb
input:
10 100 10000 8 7 2340 2 10 9672 6 5 9321 1 6 9967 3 5 8730 4 10 4620 10 6 900 10 7 2895 9 2 7152 8 7809 1 4950 5 3314 5 9980 6 8652 3 2942 3 338 5 4557 6 7854 8 3297 0 9281 5 9232 4 2377 2 4401 3 4652 2 2762 3 6834 6 3389 4 607 8 8284 7 6218 3 3302 5 3090 8 2079 4 3037 4 4930 5 5958 4 84 0 3857 8 59...
output:
36432 28142 20868 20058 18801 14426 16311 12355 11108 11146 11364 10508 11053 12134 13140 14015 13009 14495 15263 15915 15878 17829 15878 17474 16054 15179 10412 6369 6063 6072 6459 4415 3651 3015 4299 6167 6341 6167 4883 5822 4147 4257 4463 5892 5721 6873 8363 8563 7350 7756 9549 9912 10909 11354 1...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 21124kb
input:
10 100 10000 10 6 2079 3 7 9297 1 8 1844 1 10 3876 2 4 724 8 4 3142 9 8 5216 1 3 6365 6 5 5438 1 1163 5 1574 5 8933 8 8149 0 3315 1 8759 1 6558 8 7394 7 3293 8 5470 1 1788 3 8267 6 6687 5 4364 6 6339 2 2195 0 9902 1 1019 0 3513 5 3767 2 6228 6 9386 4 3821 2 8993 0 8216 7 223 8 6353 3 65 8 3806 0 339...
output:
18921 14588 16035 17077 14588 15246 15887 17364 14778 14531 15634 17400 18140 18798 19401 20749 19689 18983 19635 20541 21642 17533 16432 17770 18791 20465 21738 20064 20532 22154 23160 24201 25014 24713 23160 18870 19720 18870 13988 13153 10485 6955 8417 8952 8417 6052 5468 6827 5468 4827 3817 2131...
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 20612kb
input:
10 100 10000 10 4 7087 4 2 6092 1 10 1280 6 10 3436 7 5 7207 3 10 9966 5 3 7222 7 9 2626 8 5 64 3 8102 7 1602 7 1354 3 4207 3 1091 4 9901 2 773 8 4623 6 5147 5 859 1 4062 7 176 6 6025 3 1580 1 3667 2 1116 4 2586 8 3652 7 6522 8 6644 1 6759 4 7015 3 7560 0 255 1 7252 4 6105 0 7220 0 7925 6 8215 8 851...
output:
40200 34795 36516 30017 21281 16082 16139 16082 16203 17116 14482 14712 9086 8324 9133 7660 6677 4380 3480 3358 3089 2470 2171 3586 4300 2885 2152 1878 1598 1280 1201 1036 704 886 2002 3439 4198 3449 3457 3529 4211 5623 6794 5415 3760 5497 3833 3063 5055 4780 3558 3421 5321 7024 5321 5732 7201 8503 ...
result:
ok 100 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 20568kb
input:
10 100 10000 7 2 9990 7 4 2933 6 9 131 2 5 4180 10 8 6036 2 10 8488 6 1 4703 8 3 6095 10 9 4297 0 1000 3 2262 2 7136 2 3590 4 3067 5 6332 8 1725 2 7171 2 235 8 7936 6 4285 1 6527 0 8091 6 9291 0 7002 4 6236 3 8768 3 5378 5 569 8 7107 8 7489 7 8198 3 807 0 4058 1 8692 2 5076 6 6283 1 7531 3 7509 2 43...
output:
24799 25765 27419 23453 24139 22053 23554 22868 23038 23541 25363 23475 21653 14206 14109 11351 10526 12133 13861 12713 12181 10670 6243 3842 5155 3842 3848 4926 5982 4875 5298 4875 3049 5025 4963 5560 7171 5686 5867 4633 4654 5642 4615 3146 2109 3966 4941 6460 7078 8396 7078 8496 7078 8820 7078 730...
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 19752kb
input:
10 100 10000 8 6 7957 2 5 5987 3 4 5488 1 7 8065 1 10 3293 8 7 8749 5 9 4304 6 2 5044 3 9 8563 6 5249 7 9130 4 5387 8 9525 0 4056 2 8845 6 5697 7 8725 5 890 4 4993 6 9360 5 4084 2 6375 8 4887 5 4499 3 1805 6 6743 3 7695 0 5857 4 6049 0 3692 0 8853 8 6096 1 825 8 1736 3 9910 0 6311 5 8424 8 153 6 259...
output:
58395 59933 60004 61576 62164 55108 50281 50538 43403 42270 42891 44378 37606 38469 40009 41018 41804 43542 44545 42171 42714 34882 29997 30066 22862 23832 22408 20747 20825 21477 19845 16992 9393 9919 11716 12657 12208 11394 12034 9655 10980 11366 13039 13942 9929 7869 8222 7490 7268 9211 10641 106...
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 3ms
memory: 19524kb
input:
50 100 10000 1 8 6341 24 13 9970 49 33 8948 8 4 7841 37 20 8622 14 20 9574 1 46 1759 3 48 9588 41 42 3168 47 34 541 20 22 7825 15 21 2424 9 20 6679 42 15 9261 23 1 31 49 15 1996 45 16 1249 44 32 9036 22 15 2694 23 30 8009 27 9 7800 19 11 6125 20 38 6891 28 39 5247 16 3 8141 32 7 8846 5 23 8802 33 31...
output:
59373 57016 56924 57577 53308 53308 48777 46985 46985 43203 43203 43203 42550 42550 43083 43083 43083 42620 42550 42550 43143 42550 42337 42341 42316 41873 41873 41007 39527 39527 38947 40534 37801 37290 35302 35167 35011 33876 33445 34000 33445 35412 35412 36991 36991 31048 29469 28542 26975 26886 ...
result:
ok 100 lines
Test #8:
score: 0
Accepted
time: 3ms
memory: 21136kb
input:
50 100 10000 14 36 8043 38 22 6480 20 31 8990 5 24 2043 18 9 2214 26 38 8713 41 23 6057 5 31 903 49 42 517 26 33 1587 37 42 4755 39 11 8913 41 33 6066 4 46 6565 2 50 8961 23 40 378 12 48 5060 23 44 7471 30 38 7648 1 50 1632 21 36 5084 46 8 5537 45 38 342 4 40 1009 29 30 6257 5 25 1758 7 9 7620 32 5 ...
output:
65340 65340 65340 63827 63377 63198 60867 60867 58144 55446 55044 49538 45973 45478 45155 44979 36810 36810 36734 36765 37640 36734 36734 36734 36655 37757 37757 36705 36895 36895 36376 36376 31986 30519 29916 30980 32184 30980 30980 32498 30980 30980 32351 32290 30600 29229 30974 30937 30814 29761 ...
result:
ok 100 lines
Test #9:
score: 0
Accepted
time: 2ms
memory: 20756kb
input:
50 100 10000 29 17 2564 39 21 1298 14 5 9449 2 21 1199 38 41 6753 40 41 8801 29 26 8632 8 47 3255 29 16 4295 49 12 8311 23 1 8208 29 38 3352 21 33 1428 38 48 8213 9 43 3270 25 35 6960 48 39 609 4 13 6052 22 27 5805 7 30 5559 43 42 4831 15 7 8844 41 34 2125 25 38 7617 44 29 9650 47 34 4943 37 24 3401...
output:
61183 61183 61183 61183 61183 58904 59303 59625 59979 59979 57513 57513 55189 52099 52606 53986 54067 54067 54683 52796 53860 51883 49202 49202 49202 48586 47093 48598 50425 52022 51509 49667 47720 48342 48342 48342 48180 47558 47558 41557 41673 41673 38432 38432 35747 36780 37433 37509 36004 35102 ...
result:
ok 100 lines
Test #10:
score: 0
Accepted
time: 2ms
memory: 20088kb
input:
50 100 10000 23 35 3588 8 14 6083 47 40 8627 48 11 1180 44 11 9818 25 45 5998 32 30 5129 33 5 9875 21 49 512 4 38 6261 1 2 8102 44 7 1612 48 30 2053 10 45 3855 38 40 7901 23 18 6194 4 1 1904 19 2 5487 37 11 1684 5 43 1668 17 13 2225 18 21 1117 50 40 6657 27 2 8189 36 16 5219 40 22 1664 25 24 6901 2 ...
output:
63266 63266 63266 63613 63266 60588 60823 57775 55943 53775 54216 54663 54092 54092 54451 54451 53563 53563 51577 53432 51087 50927 50927 49028 49028 49028 48674 48674 46750 46589 46589 47900 46589 46589 47547 48656 49278 50809 51360 51819 51268 47812 47124 44835 45416 43249 40132 42119 42119 41915 ...
result:
ok 100 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 19548kb
input:
50 100 10000 8 33 8108 31 27 7736 45 25 5415 45 26 4388 24 44 4358 43 24 6086 5 8 488 27 1 2228 12 23 4290 29 40 2986 44 46 5607 26 41 6049 11 42 3363 39 42 1451 33 50 9045 49 23 5941 1 40 3401 23 2 6852 16 24 9840 45 32 8760 19 8 8300 47 7 1261 5 17 8440 6 1 7962 47 33 8611 32 5 797 28 50 6352 21 3...
output:
95490 89008 89991 89991 89287 81988 81005 74056 67874 67188 68488 68488 69849 67552 66383 63536 64540 64839 64540 65813 63546 63549 62273 62273 63333 62005 62005 56528 58067 56865 58360 55001 55001 50551 50551 48293 48090 48637 40508 38884 39212 39414 38867 38867 40031 39703 39703 38334 37839 37663 ...
result:
ok 100 lines
Test #12:
score: 0
Accepted
time: 2ms
memory: 19624kb
input:
50 100 10000 47 30 8790 7 25 798 36 2 4178 6 1 7230 37 28 4944 46 31 6454 42 19 4628 2 3 575 37 8 501 48 50 5485 18 40 7526 49 12 1225 1 38 7968 16 21 3693 19 22 9021 15 20 477 29 24 8580 9 20 6301 31 45 4936 44 4 1556 38 25 9065 5 33 2779 39 14 2783 9 39 3551 26 48 9837 32 26 8413 36 8 3085 35 15 7...
output:
238816 230759 231869 233233 234267 234462 236311 237391 230870 232761 226894 218012 210534 211196 204159 205164 206494 206617 207073 203120 197476 191757 192067 193574 190918 191250 193069 188162 189303 182859 184239 179090 180694 181787 179143 179312 172449 165832 163911 157687 158272 149807 141376...
result:
ok 100 lines
Test #13:
score: 0
Accepted
time: 2ms
memory: 20016kb
input:
100 100 10000 61 46 59 68 17 1088 35 99 9 66 81 530 76 5 2805 29 20 1912 22 25 8237 8 72 7557 29 53 4647 100 65 5747 18 63 2645 62 68 9971 29 41 6386 85 29 9987 40 37 4983 25 48 6284 9 13 2890 74 60 3011 38 15 9519 84 83 9063 72 26 7027 20 42 6734 14 33 1615 100 84 8907 38 98 5026 11 84 9389 38 54 5...
output:
67064 67064 68098 66515 60155 60687 60687 59475 59470 60112 60112 55506 55506 55506 54429 53890 53345 53345 53450 53450 53450 53450 53450 54974 54778 51173 51917 51917 49375 51099 49375 48174 47430 47819 46427 46294 46294 45854 45755 47068 46096 46096 45990 40425 39843 41085 40521 39279 39279 39712 ...
result:
ok 100 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 19532kb
input:
100 100 10000 26 76 4133 40 44 8072 10 72 8851 75 74 1662 55 68 7054 76 35 8429 25 88 7343 82 68 9352 3 99 9320 90 12 5811 70 69 771 38 11 8024 100 98 9522 81 24 6184 51 92 454 31 89 1490 67 68 4980 88 91 4639 4 51 1134 83 56 2659 73 58 6010 68 1 2206 36 58 3853 21 35 1228 14 6 7321 91 77 7493 8 60 ...
output:
72732 70065 70509 70065 67886 65897 65796 64035 64035 61803 61941 61803 61803 61803 61803 60515 60515 56756 55601 55244 53355 51745 51544 51596 51544 50919 50255 50255 51970 52342 51970 51970 51494 49115 49674 49674 49674 49115 50267 51627 48009 45785 46361 45642 45152 45152 45609 45609 47348 47348 ...
result:
ok 100 lines
Test #15:
score: 0
Accepted
time: 2ms
memory: 20336kb
input:
100 100 10000 90 9 4002 14 12 6088 49 37 6540 42 82 4492 45 26 6755 39 71 2749 52 31 9121 16 91 7670 69 81 1294 52 57 839 62 78 6551 20 85 5721 54 4 3361 53 96 1197 6 37 9230 89 11 4113 59 33 8247 7 69 158 64 57 3585 94 6 1392 66 6 4702 85 11 9207 71 61 4590 58 17 540 66 56 3054 81 77 222 81 95 9456...
output:
91841 83535 78275 74063 73998 73998 73271 73091 73067 70590 70590 70590 70590 68753 68753 60021 56298 57074 57787 58470 58095 59455 58095 58095 56636 56636 56636 55200 56995 56995 58400 58400 58400 55360 53287 55195 56009 56009 56009 55825 55825 56326 58032 56326 55825 57594 55825 55825 56299 56299 ...
result:
ok 100 lines
Test #16:
score: 0
Accepted
time: 2ms
memory: 20728kb
input:
100 100 10000 92 93 7615 42 98 1357 70 55 1976 19 13 8638 54 11 1383 9 77 3292 7 56 9011 3 85 7376 59 75 5769 67 2 6967 5 9 2540 80 4 6902 57 90 6087 29 8 7017 49 83 2157 28 12 131 45 17 8644 72 45 2764 26 30 13 29 36 7727 28 16 6818 23 26 7000 43 94 7223 72 33 8545 100 87 6232 54 39 3305 36 62 9880...
output:
88621 86102 80364 75016 75016 75232 75232 76458 76458 76458 76458 73584 73584 71627 71415 68686 68686 68363 68734 69433 65213 65213 62047 61676 59310 59106 59493 58982 58595 60004 58595 59419 58595 60108 59055 56053 54540 50387 49992 48679 50114 50114 50114 50114 51380 51828 50077 50077 50058 48948 ...
result:
ok 100 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 19468kb
input:
100 100 10000 19 26 1536 85 56 9371 14 39 5613 32 82 7798 71 3 3868 68 1 4447 85 62 7625 80 12 9746 68 23 4958 41 47 8831 53 25 5536 94 40 4598 75 49 6761 55 92 2029 42 69 934 35 7 5539 91 7 5963 22 65 1447 89 60 5248 21 84 6460 91 6 2347 76 88 6279 82 59 5177 49 57 4692 49 76 2852 71 46 2869 86 63 ...
output:
208612 201077 198582 198582 199864 194192 194192 194192 190022 190022 185574 180889 181928 180986 181866 181866 181866 181866 181866 175063 175729 172365 169399 169399 169399 169399 170172 166385 167243 167243 159394 155158 155659 147284 139152 135701 131742 130957 130957 128260 120349 115491 114864...
result:
ok 100 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 19868kb
input:
100 100 10000 24 12 9297 78 40 7121 35 37 2272 11 45 8083 41 47 9047 49 10 654 62 79 708 86 89 4880 94 95 7215 73 7 6235 15 52 7117 42 70 6983 100 80 8304 92 99 658 72 51 5005 39 19 9178 70 25 1106 5 62 327 16 69 5998 80 15 2986 31 1 1817 22 68 1184 81 50 7427 47 71 6537 28 86 6754 17 91 944 65 25 9...
output:
469366 464225 464020 458417 459843 454980 449438 449836 450811 443374 445256 447049 447320 448664 450613 443925 437069 431483 431612 426901 421627 412880 411253 412135 413487 414011 414578 414683 415435 415698 415886 413640 414380 416346 417861 408790 408111 402662 402780 404244 405877 401314 401655...
result:
ok 100 lines
Subtask #2:
score: 13
Accepted
Dependency #1:
100%
Accepted
Test #19:
score: 13
Accepted
time: 3ms
memory: 20832kb
input:
1000 5000 10000 69 162 9125 754 571 3839 370 417 1897 43 6 5179 470 808 4807 488 100 464 65 808 821 962 340 197 886 736 9712 692 808 9775 794 712 160 120 32 2229 15 829 5889 932 174 2327 995 833 8691 452 628 2146 52 336 5777 24 235 3472 508 973 5060 431 537 4485 738 746 5757 761 609 3687 956 391 654...
output:
153826 150298 145424 143019 143019 142930 142484 142349 140965 140965 140965 140912 140912 138310 138310 138310 132967 128421 122670 122277 119897 115547 115547 113138 113011 112481 112481 112481 112481 112481 112481 112194 112194 110289 107027 106281 105633 105846 105094 104881 104881 103103 102708...
result:
ok 5000 lines
Test #20:
score: 0
Accepted
time: 3ms
memory: 20104kb
input:
1000 5000 10000 839 5 9470 237 599 4211 766 305 9104 603 890 1978 421 816 3026 125 966 492 766 927 7564 216 747 1373 752 111 7864 54 88 4214 223 70 945 427 925 3824 800 347 8708 272 814 1949 290 226 648 302 834 7026 569 784 9705 214 166 2534 15 100 5222 522 874 3217 817 680 8649 197 805 7036 921 41 ...
output:
344717 344717 344717 344717 344717 339327 339327 339327 334468 326101 319241 319241 317331 317331 314536 314536 305972 305972 305972 305972 305287 305287 305287 305287 304043 302529 302529 302529 298136 298136 296587 294807 294807 294763 294763 294763 289154 289154 286073 283462 283462 283462 279593...
result:
ok 5000 lines
Test #21:
score: 0
Accepted
time: 5ms
memory: 20668kb
input:
1000 5000 10000 854 284 7936 773 935 334 325 335 3105 464 462 6440 199 119 9945 378 792 4664 863 421 2574 343 775 3689 466 392 9674 501 472 2616 618 770 9283 813 592 9010 554 913 7723 527 214 4371 878 906 3615 164 628 9207 289 354 8279 478 38 94 100 322 9646 234 286 6661 347 732 903 833 629 9581 234...
output:
1061320 1054121 1054392 1050732 1050732 1045321 1036714 1028024 1028024 1028024 1029374 1028748 1029156 1029156 1026270 1026270 1027444 1027444 1023630 1020690 1020690 1020690 1020690 1016789 1009969 1009969 1010146 1006927 1006927 1006927 1007140 1007140 1008770 1008770 1008770 1008770 1005883 1003...
result:
ok 5000 lines
Test #22:
score: 0
Accepted
time: 5ms
memory: 20988kb
input:
1000 5000 10000 433 889 4613 319 153 5207 498 263 3697 223 689 8873 848 890 3842 679 676 2837 41 276 4924 205 248 5967 638 693 4171 382 182 8898 331 828 6704 717 788 1739 615 74 390 475 935 953 977 484 9822 121 158 7196 208 253 4342 947 806 3956 992 778 9706 329 100 4173 681 20 29 66 645 463 122 602...
output:
4984011 4977789 4972772 4968128 4963697 4960087 4953993 4946386 4947212 4942402 4942854 4940038 4937819 4936391 4934166 4927219 4921110 4917436 4910332 4905433 4903788 4904318 4899408 4894941 4891316 4884779 4885526 4881283 4880509 4880546 4878489 4876311 4878016 4879497 4871113 4864055 4862088 4856...
result:
ok 5000 lines
Test #23:
score: 0
Accepted
time: 6ms
memory: 22188kb
input:
5000 5000 10000 1481 2855 8677 1142 1253 4998 1165 1236 9935 4676 503 4299 3953 3357 9173 2640 1670 9762 206 4314 7246 583 1150 5038 1809 2354 6461 782 3552 729 1161 3871 4368 1429 4570 7936 59 34 835 4456 4439 2475 4156 2892 5214 2861 2024 1151 1254 1293 3574 2504 699 1227 4850 1234 4793 3104 3880 ...
output:
175492 175465 175465 175465 175465 175465 175465 170712 166703 166703 163136 163136 162192 157525 157525 154387 154387 154387 154387 154387 153774 153118 153118 152642 152642 152642 150341 150341 149513 147454 146817 143735 143735 143735 143735 143735 142635 142635 142635 142450 141843 141843 141095...
result:
ok 5000 lines
Test #24:
score: 0
Accepted
time: 7ms
memory: 22108kb
input:
5000 5000 10000 434 1228 9487 4886 3793 6369 921 189 4961 167 4942 5072 2564 3914 3037 731 3810 3375 579 1439 5969 3411 320 928 1933 2357 1326 3771 4776 4444 4718 628 2771 2635 1323 7392 796 4049 6758 3570 4552 739 3590 1624 3201 1112 2679 1007 2957 1426 2617 120 899 7244 3440 1101 3750 869 852 6180...
output:
1225078 1225078 1218100 1210219 1210219 1210219 1202012 1196589 1196589 1189777 1183406 1177496 1173050 1173050 1173050 1167164 1167164 1162626 1162626 1162626 1162626 1155409 1152472 1144004 1144004 1135926 1135926 1135926 1135926 1129700 1130192 1130192 1130192 1124937 1124937 1124937 1124937 1124...
result:
ok 5000 lines
Test #25:
score: 0
Accepted
time: 6ms
memory: 20912kb
input:
5000 5000 10000 8 2771 1668 3242 3996 211 4507 3917 2074 1041 973 5212 2202 2310 4789 2314 2790 2154 2000 70 5186 2322 4923 2250 168 3633 6046 4288 2302 3238 384 1353 9598 814 3014 5671 3411 4009 9639 1322 455 4153 309 2120 2332 4878 582 844 2187 4883 8097 2035 3031 5512 1500 2337 1065 2273 2047 689...
output:
5028494 5028494 5024074 5017639 5014510 5008398 5008398 5005471 5005471 5005471 5005471 4997165 4997165 4997165 4993066 4988583 4984746 4984746 4980100 4980100 4971199 4967111 4967925 4964358 4964358 4964358 4961371 4954065 4954065 4946629 4946629 4939866 4939866 4932868 4926314 4926314 4926314 4922...
result:
ok 5000 lines
Test #26:
score: 0
Accepted
time: 7ms
memory: 22572kb
input:
5000 5000 10000 479 413 3559 4440 1056 9179 4812 1670 4672 2641 4347 9162 1908 3453 566 4030 4422 6438 343 372 2726 139 4054 395 2501 2984 1994 4507 1715 9090 4431 2766 4230 2853 197 479 1891 1440 3579 1665 4719 2700 2666 3750 3299 3620 4314 6471 1505 165 183 3212 3236 7734 2266 3246 5551 2797 4437 ...
output:
24741883 24737777 24738317 24739894 24741048 24741903 24742838 24743812 24741227 24738214 24735683 24735723 24737644 24738320 24740167 24740534 24741988 24733901 24735689 24737307 24732570 24733604 24734172 24734997 24731190 24731728 24724478 24725573 24726937 24721049 24721654 24721557 24712784 247...
result:
ok 5000 lines
Subtask #3:
score: 7
Accepted
Test #27:
score: 7
Accepted
time: 0ms
memory: 19232kb
input:
20 20 10000 1 2 835 1 3 57 1 4 1883 1 5 1349 1 6 1543 1 7 688 1 8 272 1 9 744 1 10 569 1 11 1019 1 12 201 1 13 1228 1 14 1194 1 15 1123 1 16 48 1 17 164 1 18 893 1 19 963 1 20 818 6 1 0 7412 10 6575 15 6696 0 7412 4 8318 18 7563 15 7502 1 7668 13 7859 14 8045 2 7969 12 8159 11 8040 2 8168 12 8192 0 ...
output:
3426 3426 3426 2892 2577 2577 2543 2472 2142 2142 2086 2018 1961 1961 1958 1653 1562 1432 1432 1064
result:
ok 20 lines
Test #28:
score: 0
Accepted
time: 0ms
memory: 19356kb
input:
20 200 10000 1 2 17 1 3 373 1 4 255 1 5 1243 1 6 468 1 7 1594 1 8 1375 1 9 383 1 10 36 1 11 1961 1 12 1816 1 13 1744 1 14 1611 1 15 1619 1 16 1620 1 17 144 1 18 1444 1 19 1129 1 20 1812 12 1 14 6239 16 6351 13 6228 17 6447 15 6815 10 6637 9 6762 4 6885 9 7217 18 7229 14 7381 8 7459 1 8746 18 9031 7 ...
output:
3777 3773 3773 3773 3556 3364 3239 3239 3064 2819 2687 2573 1597 1597 1757 1757 1096 851 756 776 776 776 1339 1339 776 759 759 746 746 746 624 501 416 364 805 364 270 189 112 111 107 107 1021 1620 1620 1190 360 191 121 107 103 78 172 77 588 791 588 948 509 166 729 863 1314 863 1228 863 863 774 762 7...
result:
ok 200 lines
Test #29:
score: 0
Accepted
time: 0ms
memory: 20908kb
input:
20 2000 10000 1 2 25 1 3 1900 1 4 1586 1 5 1319 1 6 219 1 7 1300 1 8 776 1 9 1051 1 10 362 1 11 1085 1 12 600 1 13 1576 1 14 315 1 15 1292 1 16 1167 1 17 1518 1 18 1911 1 19 1196 1 20 465 12 56 9 6271 1 6684 1 6622 6 6572 1 7038 3 6816 16 6979 4 8313 15 7409 5 7409 17 7710 10 7663 4 7957 17 7865 1 8...
output:
3811 3497 3487 3429 3230 3230 3211 2592 2592 2592 2496 2363 2252 2136 2136 1956 1505 1505 1267 1263 1173 1114 1630 934 1490 974 971 955 1421 955 378 470 470 728 470 378 371 1027 1190 543 534 301 301 292 290 1074 290 272 168 168 164 216 201 356 201 115 236 648 762 1241 1241 1206 1065 1500 1021 1249 8...
result:
ok 2000 lines
Test #30:
score: 0
Accepted
time: 7ms
memory: 19640kb
input:
20 20000 10000 1 2 1046 1 3 272 1 4 584 1 5 244 1 6 1124 1 7 1107 1 8 223 1 9 326 1 10 1816 1 11 891 1 12 1116 1 13 889 1 14 811 1 15 1377 1 16 636 1 17 69 1 18 1885 1 19 894 1 20 1613 2 267 12 6321 10 6503 10 6526 16 6628 14 6876 0 6939 14 7067 9 7348 6 7819 10 7891 11 7848 18 7848 1 8246 15 8316 9...
output:
3701 3498 3498 3498 3262 3262 3009 3009 2240 2223 2153 2153 1937 1780 1525 1246 1215 1527 910 882 861 424 869 869 1434 1011 424 547 547 525 691 525 384 361 286 240 477 465 210 192 186 368 1084 391 1184 1031 1374 652 309 555 484 1072 1487 1532 1597 1532 1532 1532 1487 1349 1007 913 415 413 390 215 17...
result:
ok 20000 lines
Test #31:
score: 0
Accepted
time: 15ms
memory: 20224kb
input:
20 100000 10000 1 2 499 1 3 916 1 4 1568 1 5 1135 1 6 136 1 7 1364 1 8 444 1 9 561 1 10 698 1 11 456 1 12 1543 1 13 1678 1 14 734 1 15 393 1 16 1768 1 17 1892 1 18 366 1 19 37 1 20 1051 6 354 11 6803 2 6437 6 6540 17 6688 5 6755 0 6860 11 7064 3 6998 2 7250 6 7399 1 7467 4 8496 13 9106 5 8569 2 8768...
output:
3660 3660 3570 3570 3246 3221 3042 3042 2813 2729 2594 1650 1432 1432 1259 1236 1197 1154 1064 1535 1203 1395 1203 1488 1488 1017 1132 1132 1017 1017 957 564 434 238 470 1110 1115 689 689 689 674 1180 1180 674 634 435 251 686 725 686 251 693 251 602 597 596 782 1242 1559 1265 782 1362 1420 1362 1362...
result:
ok 100000 lines
Test #32:
score: 0
Accepted
time: 0ms
memory: 20308kb
input:
2 10 10000 1 2 771 0 151 0 9855 0 9999 0 8476 0 1455 0 7763 0 3304 0 8286 0 2481 0 8467
output:
151 6 5 8481 9936 7699 1003 9289 1770 237
result:
ok 10 lines
Test #33:
score: 0
Accepted
time: 3ms
memory: 19612kb
input:
501 20 10000 1 2 1672 1 3 802 1 4 330 1 5 1394 1 6 1676 1 7 1751 1 8 417 1 9 1447 1 10 1736 1 11 956 1 12 224 1 13 203 1 14 1999 1 15 1385 1 16 1983 1 17 601 1 18 1800 1 19 1273 1 20 212 1 21 798 1 22 1535 1 23 669 1 24 1102 1 25 1117 1 26 563 1 27 1833 1 28 862 1 29 1243 1 30 1366 1 31 854 1 32 156...
output:
3989 3987 3986 3986 3986 3979 3979 3979 3974 3974 3968 3966 3966 3960 3954 3954 3952 3952 3952 3952
result:
ok 20 lines
Test #34:
score: 0
Accepted
time: 0ms
memory: 20872kb
input:
501 200 10000 1 2 392 1 3 9 1 4 1790 1 5 1700 1 6 321 1 7 1602 1 8 838 1 9 1217 1 10 1210 1 11 925 1 12 746 1 13 592 1 14 104 1 15 1647 1 16 1370 1 17 1827 1 18 709 1 19 1300 1 20 1659 1 21 590 1 22 1953 1 23 941 1 24 1653 1 25 1307 1 26 526 1 27 237 1 28 69 1 29 1993 1 30 947 1 31 396 1 32 1740 1 3...
output:
3989 3985 3985 3985 3985 3985 3980 3973 3973 3973 3970 3965 3965 3962 3948 3942 3942 3942 3942 3942 3936 3933 3933 3933 3924 3924 3924 3913 3887 3887 3887 3863 3863 3856 3856 3856 3855 3848 3848 3848 3848 3848 3845 3844 3844 3840 3840 3839 3839 3825 3821 3821 3811 3803 3803 3803 3802 3802 3796 3788 ...
result:
ok 200 lines
Test #35:
score: 0
Accepted
time: 3ms
memory: 20396kb
input:
501 2000 10000 1 2 178 1 3 1051 1 4 1631 1 5 1451 1 6 1282 1 7 1444 1 8 583 1 9 1321 1 10 1706 1 11 1108 1 12 279 1 13 573 1 14 1873 1 15 1931 1 16 1092 1 17 234 1 18 221 1 19 398 1 20 808 1 21 551 1 22 1274 1 23 982 1 24 242 1 25 1040 1 26 1018 1 27 577 1 28 451 1 29 1172 1 30 1088 1 31 1328 1 32 3...
output:
3981 3969 3968 3968 3967 3967 3964 3959 3956 3956 3951 3945 3945 3944 3938 3938 3935 3935 3931 3931 3931 3920 3920 3920 3920 3920 3910 3903 3903 3903 3903 3903 3899 3899 3893 3893 3893 3893 3893 3883 3883 3876 3875 3860 3860 3858 3858 3858 3857 3857 3857 3851 3841 3841 3838 3838 3829 3829 3829 3829 ...
result:
ok 2000 lines
Test #36:
score: 0
Accepted
time: 3ms
memory: 20196kb
input:
501 20000 10000 1 2 1385 1 3 510 1 4 1745 1 5 97 1 6 1133 1 7 1866 1 8 1058 1 9 1499 1 10 779 1 11 1822 1 12 476 1 13 1190 1 14 839 1 15 422 1 16 1534 1 17 39 1 18 56 1 19 37 1 20 1304 1 21 1161 1 22 1547 1 23 1533 1 24 1729 1 25 108 1 26 718 1 27 1784 1 28 1201 1 29 241 1 30 438 1 31 995 1 32 712 1...
output:
3994 3994 3991 3991 3991 3991 3991 3991 3986 3974 3974 3958 3958 3957 3957 3949 3949 3941 3939 3921 3921 3921 3921 3921 3906 3906 3903 3892 3887 3885 3885 3881 3881 3880 3880 3880 3880 3878 3878 3878 3873 3868 3868 3858 3841 3841 3841 3841 3837 3837 3832 3832 3832 3832 3813 3802 3802 3802 3802 3802 ...
result:
ok 20000 lines
Test #37:
score: 0
Accepted
time: 19ms
memory: 19412kb
input:
501 100000 10000 1 2 1459 1 3 960 1 4 1508 1 5 198 1 6 793 1 7 1364 1 8 1610 1 9 1201 1 10 721 1 11 840 1 12 539 1 13 1236 1 14 861 1 15 830 1 16 484 1 17 1610 1 18 272 1 19 381 1 20 1074 1 21 1921 1 22 1571 1 23 1709 1 24 408 1 25 1183 1 26 1380 1 27 1644 1 28 813 1 29 1498 1 30 1426 1 31 1276 1 32...
output:
3981 3981 3981 3981 3980 3961 3961 3959 3959 3957 3931 3931 3915 3910 3910 3910 3910 3908 3900 3900 3890 3889 3889 3882 3882 3882 3874 3874 3874 3874 3871 3868 3864 3861 3861 3855 3855 3854 3854 3854 3814 3814 3814 3814 3814 3808 3808 3808 3808 3794 3794 3779 3779 3748 3739 3739 3739 3737 3737 3737 ...
result:
ok 100000 lines
Test #38:
score: 0
Accepted
time: 3ms
memory: 20128kb
input:
5001 20 10000 1 2 1023 1 3 898 1 4 297 1 5 1041 1 6 145 1 7 543 1 8 111 1 9 1645 1 10 514 1 11 1671 1 12 1635 1 13 210 1 14 1820 1 15 311 1 16 811 1 17 373 1 18 1842 1 19 770 1 20 1106 1 21 418 1 22 168 1 23 524 1 24 950 1 25 1642 1 26 37 1 27 528 1 28 986 1 29 464 1 30 1448 1 31 364 1 32 982 1 33 1...
output:
4000 4000 3999 6886 6886 6886 6885 8630 5743 5742 3996 3996 3995 3994 3994 3994 5968 7835 5968 5968
result:
ok 20 lines
Test #39:
score: 0
Accepted
time: 7ms
memory: 21304kb
input:
5001 200 10000 1 2 1629 1 3 834 1 4 803 1 5 1119 1 6 1292 1 7 414 1 8 203 1 9 445 1 10 1644 1 11 1982 1 12 681 1 13 124 1 14 1135 1 15 671 1 16 64 1 17 1215 1 18 1594 1 19 1606 1 20 1545 1 21 314 1 22 1257 1 23 793 1 24 928 1 25 870 1 26 58 1 27 948 1 28 916 1 29 1937 1 30 126 1 31 1798 1 32 459 1 3...
output:
4000 4000 4000 4000 3999 3999 4182 3999 4033 5585 6502 4983 4033 4032 4032 3998 5276 5276 3998 5473 5473 5473 7954 6479 8685 6204 6203 6203 6203 6203 6203 7512 6203 8189 8189 6244 6203 7265 7265 7265 5058 5787 5787 4725 4725 4729 4725 5018 4725 4724 5148 4724 4723 4723 4723 3992 3991 4606 3991 3990 ...
result:
ok 200 lines
Test #40:
score: 0
Accepted
time: 7ms
memory: 20304kb
input:
5001 2000 10000 1 2 275 1 3 314 1 4 1278 1 5 1729 1 6 265 1 7 1139 1 8 782 1 9 291 1 10 821 1 11 518 1 12 93 1 13 202 1 14 1503 1 15 55 1 16 80 1 17 468 1 18 1525 1 19 1995 1 20 428 1 21 1376 1 22 426 1 23 830 1 24 255 1 25 1619 1 26 1009 1 27 702 1 28 376 1 29 150 1 30 1894 1 31 749 1 32 362 1 33 7...
output:
3999 3999 3999 3999 3999 3998 4952 4952 4952 4952 3998 5459 5800 6962 5842 5501 5501 3998 3998 3997 3997 3997 3996 3996 4685 4685 5240 5806 7048 5806 5240 6345 6211 4551 4734 4179 3996 4808 4808 4836 4836 4836 4836 4024 4024 6047 6047 6019 7327 7927 7212 5304 5302 5301 5301 6295 6295 6604 6604 7811 ...
result:
ok 2000 lines
Test #41:
score: 0
Accepted
time: 7ms
memory: 20400kb
input:
5001 20000 10000 1 2 1506 1 3 820 1 4 1164 1 5 1068 1 6 1945 1 7 527 1 8 1773 1 9 717 1 10 1836 1 11 1756 1 12 1304 1 13 221 1 14 1863 1 15 1820 1 16 410 1 17 220 1 18 554 1 19 1731 1 20 1028 1 21 465 1 22 695 1 23 1512 1 24 1995 1 25 343 1 26 1429 1 27 1335 1 28 1657 1 29 635 1 30 1328 1 31 226 1 3...
output:
4000 4000 4480 4480 4000 4000 4000 4000 4000 4000 5905 5905 4000 5035 6755 5035 4000 5785 4000 5504 6433 5504 6345 4841 5511 5511 6223 6223 6052 7200 7200 7200 6052 6052 7089 6052 6052 6346 5634 5038 4462 4450 4368 5908 5540 4000 4000 6635 8528 6635 6635 6635 3999 3998 3998 3997 3994 3992 3992 4716 ...
result:
ok 20000 lines
Test #42:
score: 0
Accepted
time: 22ms
memory: 20952kb
input:
5001 100000 10000 1 2 210 1 3 415 1 4 1274 1 5 989 1 6 1975 1 7 858 1 8 1684 1 9 1212 1 10 132 1 11 1950 1 12 1465 1 13 163 1 14 1689 1 15 602 1 16 718 1 17 402 1 18 461 1 19 1 1 20 1707 1 21 1777 1 22 715 1 23 426 1 24 1883 1 25 1174 1 26 16 1 27 161 1 28 1087 1 29 112 1 30 143 1 31 1317 1 32 1771 ...
output:
3999 4562 4671 5301 4848 6379 4848 4109 4538 4429 4429 3999 3997 5555 5554 8282 8282 5554 3996 3995 3995 3994 3994 3994 4795 4795 3993 3993 3993 3992 3992 3992 3991 3990 4192 4192 4192 4192 4192 4192 3990 4928 3990 4723 4723 4723 3990 3990 6056 3990 3990 7335 3990 3989 3989 3987 3986 3986 5168 5168 ...
result:
ok 100000 lines
Test #43:
score: 0
Accepted
time: 97ms
memory: 38060kb
input:
100000 20 10000 1 2 64 1 3 833 1 4 935 1 5 238 1 6 1902 1 7 321 1 8 1492 1 9 195 1 10 318 1 11 1579 1 12 897 1 13 840 1 14 896 1 15 1029 1 16 1747 1 17 1271 1 18 1977 1 19 1448 1 20 320 1 21 10 1 22 611 1 23 1765 1 24 275 1 25 818 1 26 1258 1 27 1724 1 28 172 1 29 1459 1 30 1792 1 31 547 1 32 558 1 ...
output:
4000 7977 7977 7977 7977 7977 4000 4000 4000 4000 11831 16066 8235 4000 4000 4000 4000 4000 4000 10747
result:
ok 20 lines
Test #44:
score: 0
Accepted
time: 99ms
memory: 37884kb
input:
100000 200 10000 1 2 1430 1 3 1072 1 4 1432 1 5 227 1 6 1304 1 7 1243 1 8 377 1 9 693 1 10 215 1 11 759 1 12 1287 1 13 1173 1 14 1679 1 15 883 1 16 1719 1 17 716 1 18 1489 1 19 785 1 20 70 1 21 1844 1 22 801 1 23 646 1 24 1601 1 25 925 1 26 585 1 27 187 1 28 1947 1 29 1052 1 30 165 1 31 1998 1 32 41...
output:
4000 4000 4000 6470 4000 7197 4000 4000 4000 8549 12069 8549 4000 4000 7704 11535 7704 7704 12142 8438 8438 13731 9293 13081 16766 13081 9293 4000 8528 8528 13865 9337 4000 4000 4000 11792 4000 4000 9725 15879 9725 4000 4000 10932 17338 10932 16773 16773 16724 17876 16736 10944 10944 4000 4000 4000 ...
result:
ok 200 lines
Test #45:
score: 0
Accepted
time: 92ms
memory: 37648kb
input:
100000 2000 10000 1 2 210 1 3 952 1 4 1579 1 5 1678 1 6 1852 1 7 519 1 8 1331 1 9 799 1 10 1625 1 11 1972 1 12 916 1 13 174 1 14 221 1 15 1695 1 16 274 1 17 603 1 18 396 1 19 1401 1 20 916 1 21 1627 1 22 1666 1 23 859 1 24 1943 1 25 439 1 26 204 1 27 1183 1 28 475 1 29 301 1 30 589 1 31 1621 1 32 18...
output:
7989 8377 7989 4000 4000 8967 4000 10886 12341 5455 5455 5455 12379 16835 16835 17381 17381 18622 18963 18963 19015 19015 18582 19122 19122 19122 19122 19727 19727 19727 19239 19187 19187 18459 18118 17738 17496 17214 17139 17139 16944 16478 16392 16249 16249 16098 17216 16098 15833 15718 15613 1768...
result:
ok 2000 lines
Test #46:
score: 0
Accepted
time: 104ms
memory: 37648kb
input:
100000 20000 10000 1 2 448 1 3 1449 1 4 1568 1 5 376 1 6 773 1 7 701 1 8 725 1 9 504 1 10 1910 1 11 170 1 12 1057 1 13 957 1 14 76 1 15 1475 1 16 1719 1 17 1922 1 18 1541 1 19 959 1 20 558 1 21 1817 1 22 547 1 23 777 1 24 50 1 25 1767 1 26 668 1 27 1854 1 28 68 1 29 163 1 30 1336 1 31 178 1 32 853 1...
output:
4692 4692 4692 4692 4000 5609 5609 5609 4000 4173 4173 4000 4000 4000 4000 6211 6211 6211 6211 4000 6529 6529 6529 4000 6809 6809 6809 9906 14221 17759 17759 17047 13020 9906 6809 11008 8199 12064 16027 17651 14022 17039 18448 18448 17039 15460 14022 16743 17482 17482 17798 17482 17482 18131 18676 1...
result:
ok 20000 lines
Test #47:
score: 0
Accepted
time: 130ms
memory: 37632kb
input:
100000 100000 10000 1 2 1360 1 3 316 1 4 1031 1 5 768 1 6 1164 1 7 111 1 8 192 1 9 1120 1 10 1394 1 11 1477 1 12 141 1 13 880 1 14 433 1 15 1500 1 16 1365 1 17 1785 1 18 571 1 19 1784 1 20 853 1 21 313 1 22 744 1 23 1410 1 24 1807 1 25 1073 1 26 498 1 27 964 1 28 1943 1 29 999 1 30 423 1 31 798 1 32...
output:
4000 4000 4000 4000 4479 4479 4000 5675 5675 5675 9824 15157 16514 17214 16514 15157 9824 8149 11776 14495 17805 15608 15086 19203 15086 7627 7627 12253 14489 14489 14489 14532 14489 13658 11422 15058 14890 14419 17275 14419 18328 14419 7156 7156 4000 10243 16084 17974 17976 17974 19483 17995 17593 ...
result:
ok 100000 lines
Subtask #4:
score: 18
Accepted
Test #48:
score: 18
Accepted
time: 4ms
memory: 19752kb
input:
1000 1000 10000 1 2 503 1 3 889 2 4 6 2 5 1468 3 6 102 3 7 464 4 8 658 4 9 1642 5 10 1956 5 11 420 6 12 1287 6 13 1051 7 14 48 7 15 678 8 16 1662 8 17 906 9 18 432 9 19 124 10 20 71 10 21 1624 11 22 268 11 23 1776 12 24 404 12 25 967 13 26 658 13 27 815 14 28 1196 14 29 1920 15 30 865 15 31 1227 16 ...
output:
24077 24129 24073 24255 24248 24175 24175 24175 23680 22461 22205 21721 21721 21710 21624 21372 21320 21300 21300 21300 21266 21204 21067 19844 19844 19607 20014 19601 19515 19261 19244 19191 19166 19166 19107 19107 19107 19074 19074 19071 19071 19071 19082 19071 19013 18375 18200 19061 19061 19061 ...
result:
ok 1000 lines
Test #49:
score: 0
Accepted
time: 7ms
memory: 19476kb
input:
1000 10000 10000 1 2 982 1 3 287 2 4 1144 2 5 1024 3 6 1485 3 7 1624 4 8 918 4 9 954 5 10 1897 5 11 598 6 12 976 6 13 106 7 14 1856 7 15 603 8 16 877 8 17 420 9 18 1629 9 19 1838 10 20 1323 10 21 1857 11 22 765 11 23 1531 12 24 1464 12 25 415 13 26 50 13 27 112 14 28 1369 14 29 47 15 30 1011 15 31 2...
output:
26037 26037 26665 26665 25619 25379 25220 25220 25220 25385 25220 25220 25471 25708 24885 24857 24058 23808 23808 23742 23742 23742 23742 23644 23576 23486 23399 23399 23399 23399 23352 23334 23240 23201 22897 22835 22835 22850 22753 22698 23153 23076 22265 22153 22269 22153 21995 21766 21766 21235 ...
result:
ok 10000 lines
Test #50:
score: 0
Accepted
time: 4ms
memory: 20416kb
input:
1000 50000 10000 1 2 1849 1 3 257 2 4 1203 2 5 877 3 6 1554 3 7 1265 4 8 546 4 9 1707 5 10 5 5 11 10 6 12 679 6 13 945 7 14 865 7 15 889 8 16 1586 8 17 1276 9 18 1707 9 19 896 10 20 1482 10 21 976 11 22 1371 11 23 1042 12 24 1770 12 25 1477 13 26 1036 13 27 906 14 28 1231 14 29 1318 15 30 431 15 31 ...
output:
26418 27339 27339 26187 25827 25827 24646 24609 24609 24609 24609 24317 24317 23596 23402 23402 23532 23532 21855 21855 21855 21652 21652 21652 21530 21379 20966 20966 20733 20978 20959 20959 21601 21601 21274 21274 21274 21261 21261 21257 21257 21257 21264 21260 21182 21262 20940 20859 20831 20686 ...
result:
ok 50000 lines
Test #51:
score: 0
Accepted
time: 28ms
memory: 20104kb
input:
1000 100000 10000 1 2 265 1 3 23 2 4 809 2 5 1174 3 6 1290 3 7 1686 4 8 779 4 9 1733 5 10 466 5 11 1466 6 12 423 6 13 430 7 14 1358 7 15 1418 8 16 1909 8 17 1762 9 18 880 9 19 1153 10 20 530 10 21 1476 11 22 382 11 23 1388 12 24 1388 12 25 1839 13 26 1296 13 27 1103 14 28 936 14 29 1374 15 30 1461 1...
output:
25679 25679 25306 25047 24659 24578 24762 24267 23040 23000 22871 22871 22871 23551 23015 22335 22047 21834 21834 21832 21390 21279 21279 21116 21116 21116 21196 21183 22126 22126 22126 21906 21906 21906 21901 21901 21847 22747 22590 22296 22712 22778 22740 22406 22750 21514 21328 21295 19690 19419 ...
result:
ok 100000 lines
Test #52:
score: 0
Accepted
time: 8ms
memory: 22200kb
input:
10001 1000 10000 1 2 1979 1 3 1993 2 4 260 2 5 559 3 6 1293 3 7 1569 4 8 757 4 9 465 5 10 85 5 11 1181 6 12 693 6 13 134 7 14 1905 7 15 143 8 16 155 8 17 439 9 18 627 9 19 985 10 20 37 10 21 785 11 22 626 11 23 835 12 24 1507 12 25 903 13 26 1546 13 27 1112 14 28 777 14 29 286 15 30 1720 15 31 1529 ...
output:
35789 35730 35730 35654 35351 35153 35368 35254 34982 34935 35283 33508 33508 33311 33407 33407 33175 32962 32962 32518 32518 32423 32317 32396 32396 32197 32197 32177 32177 32177 31884 31884 31884 31884 32428 32341 32341 32297 32066 31925 31652 31451 31695 31622 31622 31622 31622 31485 31492 31452 ...
result:
ok 1000 lines
Test #53:
score: 0
Accepted
time: 11ms
memory: 21352kb
input:
10001 10000 10000 1 2 424 1 3 445 2 4 238 2 5 1854 3 6 719 3 7 542 4 8 1607 4 9 599 5 10 879 5 11 380 6 12 595 6 13 1865 7 14 1556 7 15 62 8 16 1920 8 17 685 9 18 1631 9 19 1250 10 20 1087 10 21 1412 11 22 83 11 23 1562 12 24 712 12 25 928 13 26 1913 13 27 266 14 28 4 14 29 1096 15 30 1325 15 31 127...
output:
33061 32515 32515 32350 32037 32037 32037 31993 31852 32639 31857 31857 31789 32568 32568 32050 31561 31561 29969 29969 29969 30363 30278 30278 29899 29296 29296 29296 29077 28932 28753 28576 28564 28366 28366 29010 28926 28926 28922 28801 28758 28710 28703 28703 28644 28169 28015 28015 27891 27891 ...
result:
ok 10000 lines
Test #54:
score: 0
Accepted
time: 18ms
memory: 22748kb
input:
10001 50000 10000 1 2 1484 1 3 1119 2 4 297 2 5 411 3 6 981 3 7 1591 4 8 1235 4 9 1353 5 10 987 5 11 1792 6 12 298 6 13 1295 7 14 1461 7 15 1053 8 16 1924 8 17 1541 9 18 1709 9 19 308 10 20 1439 10 21 723 11 22 689 11 23 881 12 24 314 12 25 1990 13 26 1411 13 27 1060 14 28 762 14 29 367 15 30 553 15...
output:
36123 35747 35747 35519 35519 35519 35337 35337 35337 35854 35854 35337 35337 35013 35013 35013 34917 34874 35246 34874 34874 34702 35329 34439 34439 34355 34325 34981 35696 35696 35975 35975 35181 35181 35136 35130 35846 35533 35484 35484 33850 33652 33652 33616 33219 33048 32941 32800 32748 32429 ...
result:
ok 50000 lines
Test #55:
score: 0
Accepted
time: 35ms
memory: 21020kb
input:
10001 100000 10000 1 2 666 1 3 277 2 4 1900 2 5 365 3 6 1099 3 7 1785 4 8 1601 4 9 374 5 10 1228 5 11 1576 6 12 210 6 13 991 7 14 1335 7 15 1207 8 16 930 8 17 548 9 18 1933 9 19 415 10 20 988 10 21 1834 11 22 1632 11 23 1195 12 24 1324 12 25 23 13 26 1593 13 27 1389 14 28 198 14 29 421 15 30 1571 15...
output:
34915 34915 34915 34915 35470 35470 35366 35980 35980 35529 35126 34896 34730 34586 34586 34586 34524 34524 34524 34524 34456 34456 34456 34669 34669 35627 35627 35863 35721 35762 35721 35665 35665 36528 36382 36382 35730 36304 36304 35591 35591 35591 35591 35503 35503 35224 35537 35224 35145 35145 ...
result:
ok 100000 lines
Test #56:
score: 0
Accepted
time: 46ms
memory: 28544kb
input:
49999 1000 10000 1 2 201 1 3 1347 2 4 1667 2 5 1544 3 6 1063 3 7 292 4 8 414 4 9 1045 5 10 1927 5 11 1259 6 12 1169 6 13 702 7 14 1530 7 15 786 8 16 776 8 17 152 9 18 1334 9 19 631 10 20 1330 10 21 491 11 22 1685 11 23 1789 12 24 51 12 25 500 13 26 852 13 27 747 14 28 1667 14 29 1924 15 30 1461 15 3...
output:
44173 43774 43298 44288 43773 43773 43542 43536 43342 43342 42744 42434 42434 42410 42410 42239 42190 42190 42190 42190 42061 42061 42061 42154 42154 42154 41627 41337 41337 41277 41277 41237 41635 41635 41431 41431 41431 41199 41436 41199 40932 40926 39852 39328 39328 39278 39278 39537 39537 39229 ...
result:
ok 1000 lines
Test #57:
score: 0
Accepted
time: 52ms
memory: 28196kb
input:
49999 10000 10000 1 2 1107 1 3 496 2 4 1439 2 5 1854 3 6 1561 3 7 1088 4 8 1470 4 9 663 5 10 1321 5 11 231 6 12 433 6 13 382 7 14 854 7 15 1483 8 16 317 8 17 1069 9 18 1225 9 19 1018 10 20 1387 10 21 721 11 22 1148 11 23 1299 12 24 1801 12 25 1198 13 26 1629 13 27 1066 14 28 1238 14 29 1337 15 30 14...
output:
42456 42265 41978 41741 40791 40770 40708 40708 41245 41245 41245 41245 41245 40708 40485 40485 40405 40382 40368 40368 40368 40220 40191 40191 40100 40056 40056 40056 40014 40014 39914 39694 40033 40033 39940 39734 40300 40300 40300 40163 40163 39917 38812 38394 38394 38383 38602 38602 38489 38444 ...
result:
ok 10000 lines
Test #58:
score: 0
Accepted
time: 59ms
memory: 28868kb
input:
49999 50000 10000 1 2 566 1 3 659 2 4 601 2 5 219 3 6 526 3 7 1433 4 8 906 4 9 712 5 10 133 5 11 747 6 12 136 6 13 1221 7 14 759 7 15 1769 8 16 1810 8 17 117 9 18 1303 9 19 75 10 20 331 10 21 1328 11 22 1946 11 23 1514 12 24 1595 12 25 964 13 26 1319 13 27 1860 14 28 1996 14 29 1311 15 30 894 15 31 ...
output:
41473 41685 41473 41473 41205 40785 40185 40906 40906 40286 40234 40071 39909 39890 39890 39743 39787 39691 39609 39536 39489 39392 39392 39392 39392 39339 39339 39339 39339 39257 39232 39699 39699 39699 39681 39214 39214 39165 39165 39090 39090 39090 39090 39052 39207 38280 38277 38277 38251 37790 ...
result:
ok 50000 lines
Test #59:
score: 0
Accepted
time: 85ms
memory: 28384kb
input:
49999 100000 10000 1 2 19 1 3 1684 2 4 885 2 5 838 3 6 1823 3 7 146 4 8 182 4 9 1512 5 10 1114 5 11 53 6 12 1882 6 13 616 7 14 1274 7 15 532 8 16 1347 8 17 664 9 18 1579 9 19 1708 10 20 1205 10 21 893 11 22 1690 11 23 635 12 24 921 12 25 1137 13 26 1420 13 27 1382 14 28 1643 14 29 1970 15 30 1445 15...
output:
45001 44473 43146 43146 42519 42519 41742 41742 41730 41689 41684 41672 41606 41606 41003 40590 39723 39567 39567 39357 39350 39347 39335 39310 39310 39308 39354 39231 39231 39185 39179 39565 39565 39568 39257 39257 39257 39182 39845 39845 39818 39818 39788 39669 39669 40542 40542 40542 40542 40445 ...
result:
ok 100000 lines
Test #60:
score: 0
Accepted
time: 96ms
memory: 36808kb
input:
100000 1000 10000 1 2 956 1 3 1983 2 4 299 2 5 986 3 6 992 3 7 1633 4 8 892 4 9 1056 5 10 831 5 11 1539 6 12 401 6 13 65 7 14 498 7 15 1240 8 16 1552 8 17 362 9 18 456 9 19 1623 10 20 1407 10 21 1947 11 22 1105 11 23 651 12 24 1722 12 25 1386 13 26 84 13 27 17 14 28 1249 14 29 223 15 30 1002 15 31 1...
output:
47501 47501 46781 46781 46261 46100 46100 45964 46705 46705 46705 44263 44062 44008 44008 44835 44835 44744 44744 44593 44593 44508 44395 44395 44395 44395 44274 44274 44274 43983 43657 43657 43387 43022 42912 42830 42568 42568 42420 42225 43006 43006 42019 41820 41820 41590 41590 41588 41271 40800 ...
result:
ok 1000 lines
Test #61:
score: 0
Accepted
time: 109ms
memory: 36972kb
input:
100000 10000 10000 1 2 760 1 3 1457 2 4 501 2 5 1536 3 6 1932 3 7 1583 4 8 1722 4 9 1540 5 10 106 5 11 1069 6 12 1255 6 13 1747 7 14 1823 7 15 1324 8 16 1914 8 17 32 9 18 1449 9 19 1695 10 20 546 10 21 1986 11 22 1916 11 23 975 12 24 1174 12 25 1345 13 26 1021 13 27 1832 14 28 1278 14 29 1149 15 30 ...
output:
47138 47000 46877 46877 46762 46670 46588 46588 46276 46111 44938 44938 44727 44618 44618 44598 45153 45056 44968 44408 44387 43665 43665 43647 43647 43475 43039 43031 43031 42939 42923 42923 43748 43748 44347 44127 44127 44048 43572 43440 43440 43354 43354 43252 43170 41807 41807 41932 41807 41807 ...
result:
ok 10000 lines
Test #62:
score: 0
Accepted
time: 132ms
memory: 36764kb
input:
100000 50000 10000 1 2 219 1 3 1619 2 4 1664 2 5 1198 3 6 193 3 7 440 4 8 646 4 9 1589 5 10 919 5 11 881 6 12 254 6 13 1689 7 14 1536 7 15 314 8 16 814 8 17 1784 9 18 232 9 19 49 10 20 194 10 21 400 11 22 521 11 23 294 12 24 1672 12 25 407 13 26 711 13 27 1729 14 28 36 14 29 419 15 30 645 15 31 92 1...
output:
44514 44325 43746 43746 42875 42805 42754 42733 42691 42691 43122 43900 43900 42795 42795 41737 41737 41737 41586 41586 41586 41586 42152 41978 41901 41901 42700 41489 41443 41423 41423 41423 41423 41423 41423 41423 41423 40997 40997 40997 40966 40953 41088 40930 40930 40930 41760 41561 41969 41762 ...
result:
ok 50000 lines
Test #63:
score: 0
Accepted
time: 154ms
memory: 36760kb
input:
100000 100000 10000 1 2 1360 1 3 316 2 4 1031 2 5 768 3 6 1164 3 7 111 4 8 192 4 9 1120 5 10 1394 5 11 1477 6 12 141 6 13 880 7 14 433 7 15 1500 8 16 1365 8 17 1785 9 18 571 9 19 1784 10 20 853 10 21 313 11 22 744 11 23 1410 12 24 1807 12 25 1073 13 26 498 13 27 964 14 28 1943 14 29 999 15 30 423 15...
output:
44206 44057 44057 44007 44007 44007 44007 43714 43673 42937 42834 42679 42609 42179 42037 41862 41800 41800 41800 41800 41773 41773 41773 41771 41812 41812 41812 41812 41812 41778 41744 41744 41744 41744 41739 41739 41739 42482 42428 42428 42428 42416 42403 42295 42227 42192 42132 42132 42128 41714 ...
result:
ok 100000 lines
Test #64:
score: 0
Accepted
time: 163ms
memory: 36748kb
input:
100000 100000 10000 1 2 10 1 3 6 2 4 1 2 5 8 3 6 4 3 7 1 4 8 2 4 9 10 5 10 4 5 11 7 6 12 1 6 13 10 7 14 3 7 15 10 8 16 5 8 17 5 9 18 1 9 19 4 10 20 3 10 21 3 11 22 4 11 23 10 12 24 7 12 25 3 13 26 8 13 27 4 14 28 3 14 29 9 15 30 3 15 31 8 16 32 6 16 33 5 17 34 8 17 35 9 18 36 7 18 37 2 19 38 6 19 39...
output:
4596 12651 13619 18080 18080 18080 18712 18712 18712 18712 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 19486 1...
result:
ok 100000 lines
Subtask #5:
score: 0
Runtime Error
Test #65:
score: 0
Runtime Error
input:
100000 100000 20000000000000 36784 60773 140153248 61611 56014 4384507 39699 81699 3960320 64081 33880 136970044 38189 43550 67958946 16177 77482 151567728 90206 77109 108497900 42376 92541 75503161 10148 21587 195080992 11109 80580 11975495 8506 81405 144971319 85501 69547 59675956 72008 46890 3423...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
0%