QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#309268 | #8136. Rebellious Edge | ucup-team1631# | AC ✓ | 86ms | 15092kb | C++20 | 6.4kb | 2024-01-20 16:16:26 | 2024-01-20 16:16:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#include <algorithm>
#include <algorithm>
#include <utility>
#include <vector>
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
public:
scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
// @return pair of (# of scc, scc id)
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <vector>
namespace atcoder {
struct scc_graph {
public:
scc_graph() : internal(0) {}
scc_graph(int n) : internal(n) {}
void add_edge(int from, int to) {
int n = internal.num_vertices();
assert(0 <= from && from < n);
assert(0 <= to && to < n);
internal.add_edge(from, to);
}
std::vector<std::vector<int>> scc() { return internal.scc(); }
private:
internal::scc_graph internal;
};
} // namespace atcoder
#include <time.h>
using namespace atcoder;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
#define all(A) A.begin(),A.end()
#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)
template<class T>
bool chmax(T& p, T q, bool C = 1) {
if (C == 0 && p == q) {
return 1;
}
if (p < q) {
p = q;
return 1;
}
else {
return 0;
}
}
template<class T>
bool chmin(T& p, T q, bool C = 1) {
if (C == 0 && p == q) {
return 1;
}
if (p > q) {
p = q;
return 1;
}
else {
return 0;
}
}
#define ss second.second
#define sf second.first
using paii = pair<int, int>;
//chmin必要
/*
有向木の最小全域木を求める.
O(|V|*|E|)らしい.知らんけど
*/
template<class T>
T Chu_Liu_Edmonds_algorithm(const vector<pair<T, paii>>& E, int v, int root = 0) {//E:{重み,{start,end}} //v:|V| //root:根
vector<pair<T, int>> Vm(v, pair<T, int>(1e9, -1));
vector<int> gr(v, 0);
vector<bool> P(v, false), f(v, false);
int cnt = 0;
T res = 0;
vector<pair<T, paii>> nE;
for (auto e : E) {
chmin(Vm[e.ss], { e.first, e.sf });
}
Vm[root] = { -1, -1 };
rep(i, v) {
if (f[i]) continue;
vector<int> ch;
int x = i;
for (; x != -1 && !f[x];) {
f[x] = 1;
ch.push_back(x);
x = Vm[x].second;
}
if (x == -1) {
rep(j, ch.size()) {
gr[ch[j]] = cnt;
cnt++;
}
}
else {
bool Q = 0;
for (long long j : ch) {
gr[j] = cnt;
if (j == x) {
P[cnt] = 1;
Q = 1;
}
if (!Q) cnt++;
}
if (Q) cnt++;
}
}
if (cnt == v) {
T ans = 1;
rep(i, v)ans += Vm[i].first;
//cout<<ans<<endl;
return ans;
}
rep(i, v) {
if (i != root && P[gr[i]]) res += Vm[i].first;
}
for (auto e : E) {
int p = e.ss;
int s = gr[e.sf];
int t = gr[e.ss];
if (s == t) continue;
else if (P[t]) {
nE.push_back({e.first - Vm[p].first, { s, t }});
}
else {
nE.push_back({e.first, { s, t }});
}
}
//cout<<res<<endl;
return res + Chu_Liu_Edmonds_algorithm(nE, cnt, gr[root]);
}
void solve() {
ll N,M;
cin>>N>>M;
vector<pair<ll,paii>> G(M);
rep(i,M){
ll U,V,W;
cin>>U>>V>>W;
U--;V--;
G[i]={W,{U,V}};
}
cout<<Chu_Liu_Edmonds_algorithm<ll>(G,N,0)<<endl;
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
ll T;
cin >> T;
rep(t, T)solve();
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3520kb
input:
3 5 6 1 2 4 1 3 2 2 3 0 3 4 1 4 5 1 5 2 1 4 4 1 2 4 1 3 6 1 4 8 4 2 1000000 3 3 1 2 100 2 1 10 2 3 1000
output:
5 18 1100
result:
ok 3 number(s): "5 18 1100"
Test #2:
score: 0
Accepted
time: 46ms
memory: 3600kb
input:
50000 4 5 2 4 998973548 2 3 501271695 4 1 778395982 1 4 32454891 1 2 757288934 4 5 1 4 720856669 2 3 665098951 3 4 407461517 2 1 866914401 1 2 457859826 4 5 1 2 75288664 1 4 624893594 3 2 458973866 2 4 769074655 2 3 834773751 4 5 2 3 237060634 2 4 297307882 3 4 200383586 1 2 42856502 3 1 16574713 4 ...
output:
1291015520 1530420294 1534956009 480300722 1366795927 1541095843 2493849488 858095911 1034153425 793861088 605832428 1051598350 612891589 1265994009 517769091 1678219738 1556463491 93634961 960978736 984886788 1696503797 1002892611 1969660290 1431417780 1515267731 977157479 1937478556 654475526 1401...
result:
ok 50000 numbers
Test #3:
score: 0
Accepted
time: 68ms
memory: 3556kb
input:
50000 4 6 1 3 754771977 2 3 517886121 1 4 392356144 1 2 702785740 3 4 888230940 2 1 829304957 4 6 2 4 255940037 1 2 380616616 1 4 819140865 3 4 36965607 1 3 496378345 4 3 652252309 4 6 2 4 179216787 4 2 401136502 1 2 715271531 1 3 859345710 3 4 24470489 1 4 148650889 4 6 3 2 20348069 1 2 152861663 1...
output:
1613028005 913960568 1284952701 1294564551 199037829 1236121455 983447828 1161647829 1289612543 2444304029 431872921 1272140390 949528400 2328941976 696541797 363553357 999320657 2221495861 879052116 1287531701 912524980 1072419431 1187727045 1571845059 1184110956 1136184594 430092563 1132894799 962...
result:
ok 50000 numbers
Test #4:
score: 0
Accepted
time: 30ms
memory: 3520kb
input:
25000 8 8 5 3 903349949 5 6 230898386 6 7 456285865 2 3 235279998 3 8 75554555 1 2 534445049 2 5 91984463 3 4 930308596 8 8 4 8 542820075 2 1 505042427 1 2 383870408 1 4 115526736 2 5 120351002 4 7 303640587 2 3 343568518 1 6 643773351 8 8 1 2 362133720 1 3 865161709 2 4 418085685 2 5 431348178 1 6 ...
output:
2554756912 2453550677 3352164037 2548011007 2946870949 2974098273 3702415713 3077518439 3933251840 3561133042 3661712043 3019312810 3492992897 3247019175 2091050366 3228447489 4450182982 4547489101 2740661646 3507248157 3421959708 3851505640 4373872101 3925763540 4160440497 2854028840 2797343113 338...
result:
ok 25000 numbers
Test #5:
score: 0
Accepted
time: 56ms
memory: 3520kb
input:
25000 8 9 1 3 8441923 2 8 804745873 1 4 814834377 1 5 576030519 8 5 953473409 2 6 714140471 2 5 77120962 1 2 511057482 4 7 145441656 8 9 1 2 276813465 4 5 165256724 1 4 522691074 1 7 417909938 1 8 962962225 1 3 805076553 2 6 623033783 8 4 647061395 3 4 815842049 8 9 3 5 20296808 3 6 597281111 1 2 76...
output:
3075782744 3773743762 3278650492 3231838190 3374994424 2926778533 4348233362 2822143392 3076722255 2596140564 2247390371 3854832394 4319882601 3180102719 3094944789 3435791714 4405129128 2340656122 2604427605 3572178751 3803314864 3351077905 3767890679 3567633269 3527865042 2895660631 3817016063 188...
result:
ok 25000 numbers
Test #6:
score: 0
Accepted
time: 36ms
memory: 3512kb
input:
25000 8 10 7 4 221904276 1 5 121915318 1 3 600836161 4 7 488300065 1 4 921802874 1 2 757229498 2 3 307033253 3 6 824028669 1 7 171060397 3 8 972502017 8 10 3 5 957779273 1 2 548128903 1 3 973419517 6 5 565445547 3 6 551907938 1 7 793064110 7 8 466118245 1 4 353130404 5 6 927135859 2 8 758403259 8 10...
output:
3375673428 4251214664 3757000574 3166584844 2788975514 2116310775 2715058780 3287246298 4025635987 3624892566 2769498633 2958022862 4290202794 2920552027 3277314894 3924975405 3237273140 2821648429 2360729796 3475710401 3972691777 4115444652 2692775193 3118467245 3132060418 2872337367 4722221967 264...
result:
ok 25000 numbers
Test #7:
score: 0
Accepted
time: 50ms
memory: 3756kb
input:
25000 8 12 2 6 449032103 1 5 646093619 7 8 888519232 2 4 749443783 4 5 475422884 1 2 434507939 6 7 525256368 3 7 280175107 6 4 267731039 2 3 727214343 5 7 91009177 1 6 499664950 8 12 4 6 657574176 1 2 5296179 5 7 312584650 3 4 999483683 2 3 491085057 2 5 719151963 7 2 741976162 1 4 636522791 1 6 458...
output:
3333436717 2807585131 4920461769 3090434252 2560790821 2380624756 2626592068 3772048085 2624368713 1844640463 2565437000 2622643735 2416136939 2618783813 2813654707 3205164529 3974831765 3722108973 2648137059 3165927114 2050934228 3202220845 3802856334 3396453248 2597210524 3975316045 2920520206 301...
result:
ok 25000 numbers
Test #8:
score: 0
Accepted
time: 31ms
memory: 3524kb
input:
200 1000 1000 239 588 133547926 183 534 928409215 241 330 641475654 535 957 589849559 10 620 614874088 309 928 569710487 3 11 494917111 543 890 68083403 400 918 317003458 251 321 376382937 147 160 903343522 452 924 589468457 20 197 468355859 108 599 820206568 230 378 910782377 220 293 903007367 115 ...
output:
497713793250 492962928026 507239162096 489416880760 498919499738 494390387999 505624748297 502273360170 487437969890 492882286087 488855359914 493516382821 492154885694 494693728666 501962518846 492234657903 499522656353 518342153867 494724608349 500831455708 498690702121 494557144727 503463772263 5...
result:
ok 200 numbers
Test #9:
score: 0
Accepted
time: 33ms
memory: 3576kb
input:
200 1000 1005 508 559 424192332 74 278 148045823 327 993 663345255 157 544 928557499 20 41 523494941 51 254 437200278 2 18 506681783 782 928 138677470 12 838 503910272 156 645 862366636 200 508 218413621 231 635 194448744 611 619 124981290 255 469 614512720 134 333 818641028 181 412 921437717 5 184 ...
output:
501129145945 508207765375 504606717649 501142420466 496433756584 508422487274 507007286774 489195446348 499101136725 504420343219 485311666315 489123709490 499113103288 496900542557 481508383246 492384657383 496513770885 509736025057 495760467649 497002983791 491910563136 494017531362 498058386677 4...
result:
ok 200 numbers
Test #10:
score: 0
Accepted
time: 75ms
memory: 3732kb
input:
200 1000 2000 39 238 864415857 26 156 707268612 146 546 499579162 417 761 332452795 10 410 961630809 587 745 361841763 131 716 968927701 834 888 74441039 142 781 613126744 221 273 614239182 900 945 849004495 668 938 475774163 297 748 413513365 679 862 473286635 262 523 476328885 852 977 55421955 256...
output:
377088491179 368197541228 378166264449 385285967410 363829015221 378666687744 376662529392 383676533289 374782208099 373676435135 373318306315 377833081332 386724232469 362733514349 384542854056 376214712692 376322456811 374258497868 379984477018 375276245615 384876693250 369634790945 375323862443 3...
result:
ok 200 numbers
Test #11:
score: 0
Accepted
time: 68ms
memory: 3648kb
input:
160 1000 3000 361 390 785950892 564 577 524217752 334 931 11528988 228 304 70325077 694 747 1928318 474 945 249706711 239 912 124894561 736 834 191207404 215 303 773416167 182 763 70656237 454 457 937174144 346 568 535198270 666 676 739691416 478 631 580490353 263 625 449713668 64 907 740013425 44 2...
output:
299833687308 304977657092 307270423217 294716038190 309503138234 305635005136 310814442139 312934222331 299600885716 305288964059 308283739944 300775461259 301205352773 309409716517 296295870502 294594618853 299117813318 295956044320 300467617156 305256736121 305862015525 314513636581 294398803135 2...
result:
ok 160 numbers
Test #12:
score: 0
Accepted
time: 14ms
memory: 4608kb
input:
1 1000 100000 50 415 104868280 691 700 424553918 111 968 56214986 269 529 173077590 52 117 925712505 535 560 991283286 444 729 923471207 917 964 567645976 122 305 958342700 682 945 719398103 383 527 201210989 304 318 705615051 152 926 526523918 18 527 542190718 253 593 892670139 688 706 379199924 57...
output:
23974268933
result:
ok 1 number(s): "23974268933"
Test #13:
score: 0
Accepted
time: 27ms
memory: 10132kb
input:
1 200000 200000 46957 87435 612302422 91840 173370 891722968 25009 74170 884361660 74176 99042 131797405 16139 58764 648773820 58722 191045 349784377 24095 72719 77508332 7510 25316 299592819 51067 124120 258305363 65132 104676 752760402 19337 21868 193391749 21056 155761 223617084 69406 105016 6650...
output:
100416224076541
result:
ok 1 number(s): "100416224076541"
Test #14:
score: 0
Accepted
time: 41ms
memory: 10300kb
input:
1 200000 200005 18188 18759 447257093 23283 144020 296580050 31611 45965 223988792 38100 119202 291195007 101055 137132 899526750 5591 49075 27414736 56949 151097 671413227 41985 47180 503110244 30438 46109 460979545 86928 117978 250704533 12466 168536 241962293 136066 184729 200523801 8327 161157 9...
output:
99973876572792
result:
ok 1 number(s): "99973876572792"
Test #15:
score: 0
Accepted
time: 50ms
memory: 12032kb
input:
1 200000 300000 155561 161597 537100897 126654 128124 199395618 71901 163500 259430846 142983 177985 36516674 51299 136136 392555170 27776 129030 599861396 196834 199267 608694287 10521 128879 579122252 53483 134123 144345200 101992 194707 710827766 9703 25975 222504051 40022 110651 509241864 6002 1...
output:
85802950605768
result:
ok 1 number(s): "85802950605768"
Test #16:
score: 0
Accepted
time: 59ms
memory: 13248kb
input:
1 200000 400000 83662 178071 426605522 11425 16196 19198021 143760 158308 516994131 32332 137595 862193296 49812 100060 500080963 158302 197705 152597027 31283 167752 375247059 3021 147864 874473750 79941 123131 80284324 18754 41021 30099126 20756 24387 802117779 9987 18379 197504832 8515 74052 3263...
output:
74861108824752
result:
ok 1 number(s): "74861108824752"
Test #17:
score: 0
Accepted
time: 79ms
memory: 15028kb
input:
1 200000 500000 62168 161948 861315677 112229 161852 761794094 128601 154379 526739829 62695 103637 61569219 19608 75157 292208612 126437 175609 209327426 25587 79963 853866912 40042 44741 263511253 30517 34613 381707399 159474 165977 476693969 3904 15167 805558096 4833 111840 366578074 128426 17895...
output:
66967278157139
result:
ok 1 number(s): "66967278157139"
Test #18:
score: 0
Accepted
time: 34ms
memory: 10148kb
input:
1 200000 200000 7705 8241 520782023 140531 152029 687751641 43264 43888 88402484 54060 58780 817256981 61134 74809 551055996 100583 102620 123923634 9996 11024 737292575 198215 199660 566035520 96585 97536 885236471 114899 132213 221385275 170689 175281 627663929 180974 186141 442048655 120175 15473...
output:
100188105214556
result:
ok 1 number(s): "100188105214556"
Test #19:
score: 0
Accepted
time: 30ms
memory: 10132kb
input:
1 200000 200005 68401 74132 160698844 187044 189608 214949848 197114 199326 731815192 21500 25787 694526736 72033 81952 662360391 170641 172214 362037286 156862 172151 269149013 167411 181793 485470522 147746 159804 53837947 43787 45836 194536765 107166 126965 995308582 90107 94644 185953754 21302 2...
output:
100120940177490
result:
ok 1 number(s): "100120940177490"
Test #20:
score: 0
Accepted
time: 54ms
memory: 11676kb
input:
1 200000 300000 3766 4420 373137267 116036 129195 111247661 158144 170951 883057839 61382 68089 579290706 155588 166293 639500940 136406 179216 133474469 145859 171162 167954305 116225 135112 893968344 157383 174339 956803896 59509 67116 474880072 39651 47978 385032783 67676 85713 838220071 163721 1...
output:
85256632478195
result:
ok 1 number(s): "85256632478195"
Test #21:
score: 0
Accepted
time: 67ms
memory: 13424kb
input:
1 200000 400000 120297 140098 772198011 86363 126850 879623867 120477 123540 876304344 15296 16334 590170479 169871 181898 944491242 43035 46717 562613837 16508 18292 851791484 154898 158279 489139310 145251 155084 476130469 113377 115752 830065223 160400 182101 26650956 124897 125084 88183981 18538...
output:
73541046939260
result:
ok 1 number(s): "73541046939260"
Test #22:
score: 0
Accepted
time: 82ms
memory: 15092kb
input:
1 200000 500000 17689 19395 636032584 47913 49021 217092704 90476 110562 195492702 39863 41431 281615032 115069 143751 314738997 23708 25663 329197380 128813 130925 192554235 645 680 816846550 1969 2121 51390939 25236 27260 713563693 44560 44638 811933389 110269 111129 138311338 112006 115788 436965...
output:
64199493931930
result:
ok 1 number(s): "64199493931930"
Test #23:
score: 0
Accepted
time: 33ms
memory: 10052kb
input:
1 200000 200000 80923 81029 524356932 80777 81322 605975208 184683 186275 511713894 5917 5938 478973783 197707 197912 303672471 73721 74157 121235054 80826 81371 552549792 98108 99370 613814545 20757 20782 448907956 68931 68980 465325373 105058 105507 628437785 104451 111530 579179066 50238 50753 74...
output:
99901846611220
result:
ok 1 number(s): "99901846611220"
Test #24:
score: 0
Accepted
time: 38ms
memory: 10076kb
input:
1 200000 200005 48493 48642 67041357 13578 13747 514196450 5314 5351 54673115 177461 177648 417598945 1808 1821 540881041 18745 19169 168351085 138012 138933 885329970 54521 55109 981243371 120191 120959 368416696 67553 68637 543072779 68075 68803 284380976 117151 117294 713725709 60563 61206 451262...
output:
100264161731102
result:
ok 1 number(s): "100264161731102"
Test #25:
score: 0
Accepted
time: 54ms
memory: 11732kb
input:
1 200000 300000 166609 167016 587242124 193258 195045 344428600 112992 113328 43936408 98523 98677 58792970 82293 82716 229371569 188501 189243 337557797 67991 68182 10327565 9518 9544 657592307 194099 196210 213308091 56407 56422 218843837 8971 8989 230154910 17681 17693 709463873 160780 163313 279...
output:
85348869587517
result:
ok 1 number(s): "85348869587517"
Test #26:
score: 0
Accepted
time: 62ms
memory: 13372kb
input:
1 200000 400000 35822 36031 37445407 130090 130772 163956334 54587 55569 914232449 148780 149450 259545195 126271 126300 885223403 172210 178812 909477395 166085 169466 260617947 98156 99224 97231363 135774 136578 390039658 132852 135039 884583524 186283 188032 922966484 159621 159986 11191276 1688 ...
output:
73713197570980
result:
ok 1 number(s): "73713197570980"
Test #27:
score: 0
Accepted
time: 86ms
memory: 14996kb
input:
1 200000 500000 51320 51572 662167325 76775 76862 535691105 20391 20592 831708520 116583 117444 835966021 91215 92257 327070610 101100 101762 526326742 5298 5445 707609181 73148 73313 331570053 11938 11980 110099761 14425 14459 702112118 13228 13286 53807245 83770 84606 42176590 101233 102925 549097...
output:
64270762326141
result:
ok 1 number(s): "64270762326141"
Test #28:
score: 0
Accepted
time: 30ms
memory: 10084kb
input:
1 200000 200000 109027 109045 29657209 25311 25331 280961282 15095 15096 879526875 171564 171657 801110244 198332 198558 943050198 38494 38528 759506849 52455 52526 668548339 150882 150977 821764892 166105 166162 784202684 962 963 993558513 73056 73199 720161632 107230 107282 121813839 80656 80689 4...
output:
100037565344404
result:
ok 1 number(s): "100037565344404"
Test #29:
score: 0
Accepted
time: 38ms
memory: 10280kb
input:
1 200000 200005 181668 181970 256436018 16858 16889 551412058 13501 13514 558870752 154981 155034 570222145 107709 107754 505544303 142566 142869 557172835 142867 143064 368193769 148036 148180 22660988 140714 140811 403909345 139977 139987 678168620 42532 42542 365052250 9338 9340 962914929 194309 ...
output:
100025983988963
result:
ok 1 number(s): "100025983988963"
Test #30:
score: 0
Accepted
time: 50ms
memory: 12032kb
input:
1 200000 300000 73041 73113 581820575 124415 124420 186481965 20265 20288 1071939 40389 40405 835224034 125528 125636 797450403 160939 160983 370147964 91783 91842 750913005 197184 197371 405772521 151401 151445 157054880 149686 149833 391201188 26449 26501 18657228 18818 18827 958150699 177940 1783...
output:
85291269052887
result:
ok 1 number(s): "85291269052887"
Test #31:
score: 0
Accepted
time: 59ms
memory: 13436kb
input:
1 200000 400000 47378 47429 578077719 9721 9726 429698372 181340 181603 729830543 197008 197296 663731549 136994 137019 845581874 85933 86061 972778899 189781 189797 213229077 130366 130450 345935722 119008 119048 626284190 113970 114092 53011626 171235 172369 145052487 17458 17465 36987879 55632 55...
output:
73380839092975
result:
ok 1 number(s): "73380839092975"
Test #32:
score: 0
Accepted
time: 80ms
memory: 15024kb
input:
1 200000 500000 96144 96249 622408076 17836 17859 524402519 89256 89348 242208619 147257 147318 43829213 133567 134005 313841350 103337 103382 480312838 135833 135873 222000122 78828 78870 768481944 61550 61551 572897176 162678 162681 757368039 94915 94959 756597494 51612 51734 611865481 39128 39144...
output:
64462851310914
result:
ok 1 number(s): "64462851310914"
Test #33:
score: 0
Accepted
time: 61ms
memory: 3792kb
input:
50000 4 3 1 3 167546739 4 2 150857696 1 4 51822807 4 3 3 4 741947573 1 3 900930191 3 2 716723012 4 3 1 2 606602779 2 4 794357869 4 3 982330970 4 3 4 3 742422989 2 4 962488692 1 2 664418620 4 3 1 4 320523247 4 2 225529023 2 3 338428848 4 3 3 4 231873383 3 2 240654393 1 3 81010550 4 3 1 3 426126443 3 ...
output:
370227242 2359600776 2383291618 2369330301 884481118 553538326 1420658934 1814790060 1636487543 1625309596 537349036 1752280381 1249143448 549697074 1738714045 1345620195 1811746234 1252016344 1559184113 1226822537 1088508425 1818607345 1543000967 1337019778 1710917587 1088615291 1419525376 21451014...
result:
ok 50000 numbers
Test #34:
score: 0
Accepted
time: 59ms
memory: 3600kb
input:
50000 4 4 2 4 485320476 1 4 533450041 4 2 319952928 1 3 269856374 4 4 1 3 452037325 3 4 252046806 3 2 108668947 1 4 702697785 4 4 1 4 982764378 2 3 426870264 1 3 472629382 3 2 484156411 4 4 3 2 428121575 1 4 277038145 2 3 137238069 1 3 58434493 4 4 1 4 797910962 1 3 154041077 3 2 915317132 3 4 53737...
output:
1123259343 812753078 1939550171 763594213 1606730270 1448384708 1435840093 1699368485 1622990666 1747635458 1647077177 349083873 1601005199 1200044124 1600897111 493715120 1973105265 830347364 1558171519 980872483 1159889496 1381564020 328673314 1494838829 1650465558 1706597072 2127639661 1293806849...
result:
ok 50000 numbers
Test #35:
score: 0
Accepted
time: 49ms
memory: 3552kb
input:
25000 8 7 8 3 417672786 1 2 21599197 2 7 61579086 2 6 862219611 1 4 516000641 6 8 601340576 3 5 892390154 8 7 1 5 102331144 2 7 484753283 2 6 522435371 6 8 137433435 2 4 993724737 1 2 438850997 7 3 41337395 8 7 4 3 326951219 2 5 175677503 1 4 614088417 1 2 252626863 7 8 692045913 4 6 360768250 2 7 8...
output:
3372802051 2720866362 3237880700 3810489512 3163461285 2980909825 2497241195 4090447512 4264446156 2943400684 3548026729 2420754310 2365262718 4188235331 3520414128 4758682762 2773003934 2465478547 4364902299 2837089453 3980312414 3458096134 3668063420 3466320984 3919574776 3178155812 1163610755 344...
result:
ok 25000 numbers
Test #36:
score: 0
Accepted
time: 42ms
memory: 3732kb
input:
25000 8 8 5 7 375094477 7 8 769543890 2 7 707354643 3 5 628065900 6 3 778318389 1 2 383550183 2 4 67982839 2 6 712762154 8 8 1 4 297445036 2 3 285256662 5 6 978013234 2 8 542820075 7 5 505042427 1 7 383870408 5 7 115526736 1 2 120351002 8 8 2 4 345546344 4 3 351133479 3 8 514308318 1 2 296143723 1 7...
output:
3715317832 3112798844 3755001532 2140411228 2700362971 2186342994 3896569954 2132226777 3445117101 3465410138 2859847239 2408820715 3223347980 3778898852 2955287724 1944512002 3548828964 4383818182 3641963929 3051486943 2643741932 3868672738 2981172535 3907338071 2661285694 2713366806 3681283222 332...
result:
ok 25000 numbers
Test #37:
score: 0
Accepted
time: 47ms
memory: 3728kb
input:
25000 8 9 4 2 761783123 2 5 17701951 3 8 571579765 1 3 262371757 3 4 435405018 6 7 662031263 4 7 321235114 5 6 956940778 6 8 856956563 8 9 2 4 984142283 1 3 443374148 2 6 506090462 1 2 405150481 1 5 126966728 1 7 276813465 4 3 165256724 7 8 522691074 3 8 417909938 8 9 7 2 299749140 1 4 727560020 3 6...
output:
3327017506 2882330081 3426436450 4856161143 1879345413 3924723627 2647475196 3597544154 2178732948 2991736985 2395259141 4258373242 3382943601 3413055622 3658065595 4195466826 3142022188 3050154576 3791986456 2889786725 3095576517 3022313317 3849655118 3249674750 3274732038 4131442253 3590848569 313...
result:
ok 25000 numbers
Test #38:
score: 0
Accepted
time: 45ms
memory: 3548kb
input:
25000 8 11 4 5 310801016 2 8 700412776 2 7 575120738 1 6 662936070 5 7 101970652 1 7 561178187 7 8 659200472 1 3 461223325 3 8 771048446 7 4 93795527 1 2 663341690 8 11 2 7 624226516 3 2 176804348 4 8 869811223 3 5 916207526 1 6 154691972 1 8 417052757 3 4 695860133 4 6 5171117 1 4 78421142 2 5 6608...
output:
3412476287 2031617994 2820462564 2555690868 3845528096 1273250868 3098877990 2849186057 3182065247 2548093060 3518810555 3407443473 2451021494 2900232001 2866666591 2476690805 3925732207 2837088589 4397396382 2705803951 2445581559 2331879819 2017519570 3011831045 2761773268 2545427756 2522458267 421...
result:
ok 25000 numbers
Test #39:
score: 0
Accepted
time: 31ms
memory: 3628kb
input:
200 1000 999 153 191 812234900 4 812 805855607 501 697 81669222 6 19 537590112 147 174 259281585 291 481 948109379 210 667 447645532 22 76 523130229 87 175 386067019 355 989 91593819 98 565 557738562 423 509 581708416 97 427 315550000 324 415 177404725 582 952 988308863 88 92 118563568 653 944 75412...
output:
516210868701 500339147372 499336387214 500539140603 498277310242 501870128789 516228220710 508179784194 500776602836 497921242835 492919477612 495198969705 500151411686 512678232127 498609680007 504703943889 514312309809 512391082080 501851666944 481485579079 490997584532 508254990586 493265314887 4...
result:
ok 200 numbers
Test #40:
score: 0
Accepted
time: 31ms
memory: 3620kb
input:
200 1000 1005 30 863 88714823 18 487 884033017 446 601 94705715 287 399 930520432 110 623 185303672 175 716 461853320 173 740 167694455 51 388 994769338 413 717 132438568 133 536 989798918 595 628 309881536 33 52 361860779 394 469 739975952 144 443 428165502 501 679 434395305 8 116 964768906 8 135 4...
output:
499171023112 508247421841 494457943827 499166461193 477831858402 510198184897 501804599018 489912613342 489180161029 503800514596 486384289058 491062931450 505956389976 496889211807 493521306241 495410180959 493455590717 505937787970 488658178149 493755547582 495860086984 495732583229 507614091903 4...
result:
ok 200 numbers
Test #41:
score: 0
Accepted
time: 60ms
memory: 3780kb
input:
200 1000 2000 361 390 827591830 776 839 47585307 84 230 644671754 240 419 989930465 740 767 495679446 269 607 772800035 304 547 213438009 213 519 701983575 425 464 660810298 417 456 988214235 87 215 305020871 320 926 840004627 120 747 355654476 31 232 912637512 51 159 299956132 17 618 639032414 318 ...
output:
383264959941 369564727089 378612881846 382862197562 369852605474 367664869812 369757573260 384444446217 377763334234 362860580014 377731652539 374173469154 377012364838 370185687604 361210221600 376497722261 382926313386 374481201293 381083586313 365302024664 373866228764 371915926020 381473367099 3...
result:
ok 200 numbers
Test #42:
score: 0
Accepted
time: 64ms
memory: 3952kb
input:
160 1000 3000 556 901 34261241 573 644 723615271 28 181 908355673 275 590 582558653 573 747 733152694 18 66 693688759 24 144 901311736 306 707 473045371 246 529 702959712 366 834 646714632 80 98 74112310 484 909 572977284 525 852 76259604 62 850 802999350 214 303 870204914 627 736 802553249 623 656 ...
output:
304910800107 307628976455 304898878892 293579559666 291599757403 295646210367 306439275874 307217061544 300432691868 294203617397 300889778850 304860267359 311398063102 301357064304 297677185405 300084426829 296586536032 312172515661 296778189964 305189643184 306356515331 310555718052 294050306345 3...
result:
ok 160 numbers
Test #43:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
1 3 2 3 2 0 1 3 1000000000
output:
1000000000
result:
ok 1 number(s): "1000000000"
Extra Test:
score: 0
Extra Test Passed