QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#886685 | #10066. Many Pairs | AdamGS# | 100 ✓ | 352ms | 58752kb | C++23 | 2.9kb | 2025-02-07 10:45:45 | 2025-02-07 10:45:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, LG=20;
vector<int>V[LIM];
vector<pair<pair<ll,ll>,ll>>P[LIM];
int nxt[LIM][LG], pre[LIM], post[LIM], lpre, lpost;
ll wartsyn[LIM], wartoc[LIM], ockon[LIM], sam[LIM], wyniki[LIM], wgore[LIM], poczgore[LIM], lacz;
void DFS(int x, int o) {
pre[x]=++lpre;
for(auto i : V[x]) if(i!=o) {
nxt[i][0]=x;
DFS(i, x);
}
post[x]=++lpost;
}
bool oc(int a, int b) {
return pre[a]<=pre[b] && post[a]>=post[b];
}
int lca(int a, int b) {
if(oc(a, b)) return a;
for(int i=LG-1; i>=0; --i) if(!oc(nxt[a][i], b)) a=nxt[a][i];
return nxt[a][0];
}
int pod(int a, int b) {
for(int i=LG-1; i>=0; --i) if(!oc(nxt[a][i], b)) a=nxt[a][i];
return a;
}
void DFS2(int x, int o) {
for(auto i : V[x]) if(i!=o) {
DFS2(i, x);
wartsyn[x]+=wartsyn[i];
wartoc[x]+=wartoc[i];
wgore[x]+=wgore[i];
}
}
void DFS3(int x, int o) {
pair<ll,ll>ma={0, 0};
for(auto i : V[x]) if(i!=o) {
DFS3(i, x);
if(wartsyn[i]+ockon[i]>=ma.st) {
ma.nd=ma.st;
ma.st=wartsyn[i]+ockon[i];
} else ma.nd=max(ma.nd, wartsyn[i]+ockon[i]);
}
wyniki[x]=max(wyniki[x], ma.st+ma.nd);
for(auto i : P[x]) wyniki[x]=max(wyniki[x], wartsyn[i.st.st]+ockon[i.st.st]+wartsyn[i.st.nd]+ockon[i.st.nd]+i.nd);
wyniki[x]=max(wyniki[x], lacz-wartoc[x]+poczgore[x]);
for(auto i : V[x]) if(i!=o) {
wyniki[x]=max(wyniki[x], lacz-wartoc[x]+poczgore[x]+wartsyn[i]+ockon[i]+wgore[i]);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k;
cin >> n >> k;
rep(i, n-1) {
int a, b;
cin >> a >> b; --a; --b;
V[a].pb(b);
V[b].pb(a);
}
DFS(0, 0);
for(int j=1; j<LG; ++j) rep(i, n) nxt[i][j]=nxt[nxt[i][j-1]][j-1];
rep(i, k) {
ll a, b, c;
cin >> a >> b >> c; --a; --b;
ll x=lca(a, b);
if(x!=a && x!=b) {
ll paa=pod(a, b), pbb=pod(b, a);
P[x].pb({{min(paa, pbb), max(paa, pbb)}, c});
poczgore[a]+=c;
poczgore[b]+=c;
wgore[paa]-=c;
wgore[pbb]-=c;
} else if(a==b) {
sam[a]+=c;
} else if(oc(a, b)) {
ockon[pod(b, a)]+=c;
poczgore[b]+=c;
wgore[pod(b, a)]-=c;
wgore[a]-=c;
} else {
ockon[pod(a, b)]+=c;
poczgore[a]+=c;
wgore[pod(a, b)]-=c;
wgore[b]-=c;
}
wartsyn[x]+=c;
wartoc[a]+=c;
wartoc[b]+=c;
wartoc[x]-=c;
if(a!=b) {
wgore[a]+=c;
wgore[b]+=c;
}
lacz+=c;
}
DFS2(0, 0);
rep(i, n) {
if(!P[i].size()) continue;
sort(all(P[i]));
vector<pair<pair<ll,ll>,ll>>tmp;
tmp.pb(P[i][0]);
for(int j=1; j<P[i].size(); ++j) if(P[i][j].st!=tmp.back().st) tmp.pb(P[i][j]); else tmp[tmp.size()-1].nd+=P[i][j].nd;
P[i]=tmp;
}
DFS3(0, 0);
rep(i, n) wyniki[i]+=sam[i];
rep(i, n) cout << wyniki[i] << " ";
cout << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 12
Accepted
Test #1:
score: 12
Accepted
time: 0ms
memory: 9844kb
input:
50 50 1 20 13 1 39 1 12 1 16 1 4 1 9 1 1 17 33 1 1 28 1 46 31 1 1 23 44 1 15 1 1 7 14 1 1 40 1 25 1 34 11 1 6 1 1 30 1 3 42 1 1 48 35 1 27 1 1 45 29 1 10 1 19 1 2 1 38 1 41 1 1 37 1 32 18 1 47 1 26 1 22 1 1 5 1 50 49 1 1 21 43 1 1 8 1 36 24 1 26 20 640 41 45 742 39 15 520 20 18 703 47 16 391 2 19 97...
output:
1864 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112
result:
ok single line: '1864 35112 35112 35112 35112 3... 35112 35112 35112 35112 35112 '
Test #2:
score: 12
Accepted
time: 0ms
memory: 9968kb
input:
50 50 50 1 28 1 1 15 16 1 1 38 5 1 1 23 1 42 37 1 39 1 1 4 32 1 10 1 18 1 1 19 1 36 46 1 1 34 20 1 2 1 1 26 44 1 24 1 1 30 1 43 17 1 7 1 12 1 1 22 29 1 1 3 31 1 33 1 1 14 1 49 48 1 13 1 1 45 25 1 35 1 1 41 1 21 8 1 27 1 9 1 1 40 1 6 47 1 1 11 14 19 680 44 37 476 39 12 463 16 7 354 49 41 430 38 42 77...
output:
1250 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887
result:
ok single line: '1250 32887 32887 32887 32887 3... 32887 32887 32887 32887 32887 '
Test #3:
score: 12
Accepted
time: 2ms
memory: 11888kb
input:
50 50 1 31 17 1 33 1 13 1 32 30 34 1 43 36 1 14 10 1 1 8 44 4 7 1 21 48 1 22 1 23 15 1 37 1 1 24 1 42 1 9 47 1 1 4 48 1 1 41 32 1 3 4 27 1 11 4 32 50 46 4 1 28 18 1 49 1 6 4 17 29 4 40 25 1 16 48 1 45 1 36 12 4 4 2 32 20 19 38 32 39 1 5 1 19 1 35 26 1 13 15 637 22 40 788 42 39 443 48 19 415 14 39 45...
output:
3540 31749 31749 23997 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31385 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31445 31749 31749
result:
ok single line: '3540 31749 31749 23997 31749 3... 31749 31749 31445 31749 31749 '
Test #4:
score: 12
Accepted
time: 1ms
memory: 12012kb
input:
50 50 37 31 17 9 33 21 13 36 10 30 34 39 43 28 11 14 10 42 23 8 44 41 7 19 21 24 30 22 17 23 15 24 37 20 38 24 37 42 26 9 47 11 1 4 48 32 7 41 32 4 3 39 27 38 11 21 37 50 46 14 6 28 18 44 49 8 6 11 47 29 5 40 25 30 16 39 6 45 48 36 12 2 28 2 23 20 34 38 5 39 30 5 13 19 18 35 26 18 13 15 637 22 40 78...
output:
31749 31749 31749 31749 28545 29418 31749 31749 31749 31749 29434 31749 31749 31749 31749 31749 31749 30513 31749 31749 31041 31749 26850 29829 31749 31749 31749 30766 31749 29541 31749 31749 31749 31749 31749 31749 31189 30356 30338 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749
result:
ok single line: '31749 31749 31749 31749 28545 ... 31749 31749 31749 31749 31749 '
Test #5:
score: 12
Accepted
time: 1ms
memory: 12028kb
input:
50 50 50 26 28 38 21 15 16 1 36 38 5 45 19 23 10 42 37 6 39 27 20 4 32 48 10 28 18 23 29 19 18 36 46 11 8 34 20 46 2 39 47 26 44 16 24 9 31 30 35 43 17 44 7 5 12 4 12 22 29 22 25 3 31 9 33 34 43 14 15 49 48 33 13 42 13 45 25 7 35 3 14 41 2 21 8 40 27 30 9 50 17 40 41 6 47 37 32 11 14 19 680 44 37 47...
output:
32887 32887 32887 32887 32887 32887 32887 32887 32483 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887
result:
ok single line: '32887 32887 32887 32887 32887 ... 32887 32887 32887 32887 32887 '
Test #6:
score: 12
Accepted
time: 0ms
memory: 9976kb
input:
50 50 15 20 13 17 39 43 12 50 16 27 4 45 9 42 34 17 33 44 24 28 32 46 31 5 38 23 44 26 15 35 40 7 14 13 6 40 30 25 37 34 11 29 6 49 7 30 2 3 42 10 47 48 35 8 27 22 20 45 29 25 10 3 19 23 2 19 38 31 41 14 4 37 18 32 18 48 47 11 26 9 22 12 46 5 36 50 49 1 16 21 43 41 28 8 33 36 24 21 26 20 640 41 45 7...
output:
35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112
result:
ok single line: '35112 35112 35112 35112 35112 ... 35112 35112 35112 35112 35112 '
Test #7:
score: 12
Accepted
time: 0ms
memory: 12016kb
input:
50 50 8 1 34 3 1 34 41 11 32 20 13 32 44 1 9 1 2 46 43 1 34 36 38 43 8 47 29 43 18 34 2 12 41 14 43 35 39 23 10 42 30 9 42 28 33 2 8 4 39 25 7 22 1 22 22 27 2 1 45 39 40 22 48 42 2 37 26 39 1 42 22 24 42 5 43 31 39 1 1 41 17 39 16 9 49 34 21 9 22 50 32 1 8 19 15 32 41 6 31 47 905 35 20 568 10 19 956...
output:
3187 27989 30442 30442 30442 30442 30442 28534 27565 30442 30442 30442 30442 30442 30442 30442 30442 30442 30442 30442 30442 28692 30442 30442 30442 30442 30442 30442 30442 30442 30442 28374 30442 29539 30442 30442 30442 30442 25323 30442 30004 28854 25759 30442 30442 30442 30442 30442 30442 30442
result:
ok single line: '3187 27989 30442 30442 30442 3... 30442 30442 30442 30442 30442 '
Test #8:
score: 12
Accepted
time: 0ms
memory: 9852kb
input:
50 50 50 9 38 4 3 40 14 1 7 21 27 10 29 44 47 9 25 32 15 49 12 44 23 30 11 50 25 28 35 45 36 46 32 29 37 2 12 20 5 41 45 30 37 14 17 8 28 6 3 11 1 4 24 39 21 16 35 10 34 24 48 16 41 15 40 23 43 34 43 22 31 20 7 42 19 1 39 31 36 8 19 6 46 18 48 18 5 22 38 13 17 33 26 42 2 26 13 47 3 21 797 30 28 341 ...
output:
20937 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754
result:
ok single line: '20937 33754 33754 33754 33754 ... 33754 33754 33754 33754 33754 '
Subtask #2:
score: 13
Accepted
Test #9:
score: 13
Accepted
time: 2ms
memory: 12380kb
input:
5000 500 1 2035 2103 1 2889 1 3899 1 1 1572 2838 1 1 3608 2582 1 1 2880 201 1 3989 1 1 1300 4071 1 2576 4504 1 3547 1 1145 3878 1 1 3240 1 2047 1 4983 3564 1 4965 4504 1 1305 3217 1 1 4820 2377 1 1640 1 1363 1 1 4731 1 4040 1 3707 3364 1 1 79 1 4968 2679 1 1 3276 1 4709 1 4438 1 3420 1 828 4504 4554...
output:
7043 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 3...
result:
ok single line: '7043 332097 332097 332097 3320...97 332097 332097 332097 332097 '
Test #10:
score: 13
Accepted
time: 1ms
memory: 10120kb
input:
5000 500 2967 950 1 4700 3353 2511 4023 1 1300 4532 2356 3798 1300 3894 997 4696 999 3080 35 4766 3785 2028 793 2309 63 741 1766 3785 3285 586 3353 867 3730 1 2980 3727 1065 997 2678 2375 2751 1683 4691 1400 2827 2706 1548 4078 1 1376 1443 3224 2629 4159 1552 3353 4536 1300 3103 3632 3368 865 2174 1...
output:
9048 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 318566 319126 3...
result:
ok single line: '9048 319126 319126 319126 3191...26 319126 319126 319126 319126 '
Test #11:
score: 13
Accepted
time: 1ms
memory: 12524kb
input:
5000 500 2967 3037 3043 4700 174 2511 4023 2384 1654 4532 2356 1104 386 3894 2067 4696 999 4577 35 2198 1623 2028 793 3636 63 3998 1766 2649 3285 3906 608 867 3730 247 3566 3727 1065 2247 728 2375 2649 1683 4691 4296 2827 4197 1548 2888 2904 1376 3566 3224 2629 3234 1552 3243 4536 4202 201 3632 2417...
output:
319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 318136 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126...
result:
ok single line: '319126 319126 319126 319126 31...75 319126 319126 319126 319126 '
Test #12:
score: 13
Accepted
time: 3ms
memory: 14768kb
input:
5000 500 4054 2035 2103 899 2889 2612 3899 2285 1062 1572 2838 4500 1507 3608 2582 1752 2127 2880 201 2937 3989 1262 1645 1300 4071 1650 2576 3875 333 3547 1378 1145 3878 36 1152 3240 1812 2047 188 4983 3564 3050 4965 756 1044 1305 3217 1162 3789 4820 2377 833 1640 4944 1363 263 1913 4731 2712 4040 ...
output:
332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 331221 332097 332097 332097...
result:
ok single line: '332097 332097 332097 332097 33...97 332097 332097 332097 332097 '
Test #13:
score: 13
Accepted
time: 2ms
memory: 10180kb
input:
5000 500 1507 2684 3377 3492 1 3146 2137 1967 2279 1502 1396 208 4036 4412 527 3215 2546 2615 308 598 4477 1919 4278 1250 665 3225 3124 1358 1574 1322 1092 3836 2763 1117 4183 1 208 1734 2342 2012 3058 2174 3120 376 1601 2597 2298 422 69 2437 3089 598 1117 1835 3862 1636 63 2693 2615 1195 4488 3247 ...
output:
2524 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 3...
result:
ok single line: '2524 328379 328379 328379 3283...79 328379 328379 328379 328379 '
Test #14:
score: 13
Accepted
time: 4ms
memory: 12640kb
input:
5000 500 3349 365 1199 1403 2251 3476 2517 1051 2681 3714 563 1 4526 1229 278 4460 3927 130 2542 998 2792 1306 385 4946 827 2766 3048 936 4445 1364 4164 1173 2905 4252 2211 3387 1224 733 1629 4797 1372 1208 2134 322 4269 784 1340 2808 90 4603 1313 3956 3809 3295 912 3111 2377 3500 4015 1443 674 670 ...
output:
3488 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 3...
result:
ok single line: '3488 326958 326958 326958 3269...58 326958 326958 326958 326958 '
Subtask #3:
score: 17
Accepted
Test #15:
score: 17
Accepted
time: 3ms
memory: 12352kb
input:
5000 2000 1 2035 2103 1 2889 1 3899 1 1 1572 2838 1 1 3608 2582 1 1 2880 201 1 3989 1 1 1300 4071 1 2576 4504 1 3547 1 1145 3878 1 1 3240 1 2047 1 4983 3564 1 4965 4504 1 1305 3217 1 1 4820 2377 1 1640 1 1363 1 1 4731 1 4040 1 3707 3364 1 1 79 1 4968 2679 1 1 3276 1 4709 1 4438 1 3420 1 828 4504 455...
output:
2212740 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 13...
result:
ok single line: '2212740 130540162 130540162 13... 130540162 130540162 130540162 '
Test #16:
score: 17
Accepted
time: 2ms
memory: 12628kb
input:
5000 2000 2967 950 1 4700 3353 2511 4023 1 1300 4532 2356 3798 1300 3894 997 4696 999 3080 35 4766 3785 2028 793 2309 63 741 1766 3785 3285 586 3353 867 3730 1 2980 3727 1065 997 2678 2375 2751 1683 4691 1400 2827 2706 1548 4078 1 1376 1443 3224 2629 4159 1552 3353 4536 1300 3103 3632 3368 865 2174 ...
output:
3167789 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 12...
result:
ok single line: '3167789 129909272 129909272 12... 129909272 129909272 129909272 '
Test #17:
score: 17
Accepted
time: 4ms
memory: 14456kb
input:
5000 2000 2967 3037 3043 4700 174 2511 4023 2384 1654 4532 2356 1104 386 3894 2067 4696 999 4577 35 2198 1623 2028 793 3636 63 3998 1766 2649 3285 3906 608 867 3730 247 3566 3727 1065 2247 728 2375 2649 1683 4691 4296 2827 4197 1548 2888 2904 1376 3566 3224 2629 3234 1552 3243 4536 4202 201 3632 241...
output:
129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129741991 129909272 129909272 129803447 129909272 129833295 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 ...
result:
ok single line: '129909272 129909272 129909272 ... 129909272 129909272 129909272 '
Test #18:
score: 17
Accepted
time: 5ms
memory: 14856kb
input:
5000 2000 4054 2035 2103 899 2889 2612 3899 2285 1062 1572 2838 4500 1507 3608 2582 1752 2127 2880 201 2937 3989 1262 1645 1300 4071 1650 2576 3875 333 3547 1378 1145 3878 36 1152 3240 1812 2047 188 4983 3564 3050 4965 756 1044 1305 3217 1162 3789 4820 2377 833 1640 4944 1363 263 1913 4731 2712 4040...
output:
130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130504520 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130449373 130540162 130540162 ...
result:
ok single line: '130540162 130540162 130540162 ... 130540162 130540162 130540162 '
Test #19:
score: 17
Accepted
time: 2ms
memory: 10596kb
input:
5000 2000 1507 2684 3377 3492 1 3146 2137 1967 2279 1502 1396 208 4036 4412 527 3215 2546 2615 308 598 4477 1919 4278 1250 665 3225 3124 1358 1574 1322 1092 3836 2763 1117 4183 1 208 1734 2342 2012 3058 2174 3120 376 1601 2597 2298 422 69 2437 3089 598 1117 1835 3862 1636 63 2693 2615 1195 4488 3247...
output:
585252 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131...
result:
ok single line: '585252 131912535 131912535 131... 131912535 131912535 131912535 '
Test #20:
score: 17
Accepted
time: 2ms
memory: 12480kb
input:
5000 2000 3349 365 1199 1403 2251 3476 2517 1051 2681 3714 563 1 4526 1229 278 4460 3927 130 2542 998 2792 1306 385 4946 827 2766 3048 936 4445 1364 4164 1173 2905 4252 2211 3387 1224 733 1629 4797 1372 1208 2134 322 4269 784 1340 2808 90 4603 1313 3956 3809 3295 912 3111 2377 3500 4015 1443 674 670...
output:
664106 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130...
result:
ok single line: '664106 130625863 130625863 130... 130625863 130625863 130625863 '
Subtask #4:
score: 21
Accepted
Test #21:
score: 21
Accepted
time: 1ms
memory: 14464kb
input:
5000 5000 1 2035 2103 1 2889 1 3899 1 1 1572 2838 1 1 3608 2582 1 1 2880 201 1 3989 1 1 1300 4071 1 2576 4504 1 3547 1 1145 3878 1 1 3240 1 2047 1 4983 3564 1 4965 4504 1 1305 3217 1 1 4820 2377 1 1640 1 1363 1 1 4731 1 4040 1 3707 3364 1 1 79 1 4968 2679 1 1 3276 1 4709 1 4438 1 3420 1 828 4504 455...
output:
46132009 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 26490...
result:
ok single line: '46132009 2649064843 2649064843...49064843 2649064843 2649064843 '
Test #22:
score: 21
Accepted
time: 5ms
memory: 12840kb
input:
5000 5000 2967 950 1 4700 3353 2511 4023 1 1300 4532 2356 3798 1300 3894 997 4696 999 3080 35 4766 3785 2028 793 2309 63 741 1766 3785 3285 586 3353 867 3730 1 2980 3727 1065 997 2678 2375 2751 1683 4691 1400 2827 2706 1548 4078 1 1376 1443 3224 2629 4159 1552 3353 4536 1300 3103 3632 3368 865 2174 ...
output:
71850241 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 26492...
result:
ok single line: '71850241 2649293842 2649293842...49293842 2649293842 2649293842 '
Test #23:
score: 21
Accepted
time: 3ms
memory: 12508kb
input:
5000 5000 2967 3037 3043 4700 174 2511 4023 2384 1654 4532 2356 1104 386 3894 2067 4696 999 4577 35 2198 1623 2028 793 3636 63 3998 1766 2649 3285 3906 608 867 3730 247 3566 3727 1065 2247 728 2375 2649 1683 4691 4296 2827 4197 1548 2888 2904 1376 3566 3224 2629 3234 1552 3243 4536 4202 201 3632 241...
output:
2649293842 2649293842 2649293842 2649293842 2646227721 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2645738482 2649293842 2649293842 2645969915 2649293842 2648356916 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 264...
result:
ok single line: '2649293842 2649293842 26492938...49293842 2649293842 2649293842 '
Test #24:
score: 21
Accepted
time: 6ms
memory: 10936kb
input:
5000 5000 4054 2035 2103 899 2889 2612 3899 2285 1062 1572 2838 4500 1507 3608 2582 1752 2127 2880 201 2937 3989 1262 1645 1300 4071 1650 2576 3875 333 3547 1378 1145 3878 36 1152 3240 1812 2047 188 4983 3564 3050 4965 756 1044 1305 3217 1162 3789 4820 2377 833 1640 4944 1363 263 1913 4731 2712 4040...
output:
2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2648921221 2649064843 2649064843 2648209327 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 264...
result:
ok single line: '2649064843 2649064843 26490648...49064843 2648638772 2649064843 '
Test #25:
score: 21
Accepted
time: 4ms
memory: 12732kb
input:
5000 5000 1507 2684 3377 3492 1 3146 2137 1967 2279 1502 1396 208 4036 4412 527 3215 2546 2615 308 598 4477 1919 4278 1250 665 3225 3124 1358 1574 1322 1092 3836 2763 1117 4183 1 208 1734 2342 2012 3058 2174 3120 376 1601 2597 2298 422 69 2437 3089 598 1117 1835 3862 1636 63 2693 2615 1195 4488 3247...
output:
7623187 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 261824...
result:
ok single line: '7623187 2618247942 2618247942 ...18247942 2618247942 2618247942 '
Test #26:
score: 21
Accepted
time: 5ms
memory: 14992kb
input:
5000 5000 3349 365 1199 1403 2251 3476 2517 1051 2681 3714 563 1 4526 1229 278 4460 3927 130 2542 998 2792 1306 385 4946 827 2766 3048 936 4445 1364 4164 1173 2905 4252 2211 3387 1224 733 1629 4797 1372 1208 2134 322 4269 784 1340 2808 90 4603 1313 3956 3809 3295 912 3111 2377 3500 4015 1443 674 670...
output:
11297999 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 26421...
result:
ok single line: '11297999 2642116713 2642116713...42116713 2642116713 2642116713 '
Subtask #5:
score: 37
Accepted
Test #27:
score: 37
Accepted
time: 182ms
memory: 53104kb
input:
200000 200000 1861 126068 196536 190176 143836 3918 183352 173153 149804 74098 192775 110127 106287 1861 103451 149418 160851 35753 171988 21209 156996 161848 138469 165694 35753 140239 100453 199546 110790 120346 73215 149224 19332 138469 72674 21209 127832 142648 86197 174308 181332 15643 148621 1...
output:
1640901879 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105...
result:
ok single line: '1640901879 105069892770 105069...2770 105069892770 105069892770 '
Test #28:
score: 37
Accepted
time: 193ms
memory: 51500kb
input:
200000 200000 2382 192403 197579 147684 194742 148325 1 56247 1 175826 20450 169843 56282 157962 35439 23148 167857 188718 39400 148325 113907 141255 46371 171533 167857 72544 22484 2862 168483 179717 129650 84687 125504 68013 157962 141158 38125 97780 142578 107221 144112 197794 18220 141625 178525...
output:
452919450 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 1049...
result:
ok single line: '452919450 104912193174 1049121...3174 104912193174 104912193174 '
Test #29:
score: 37
Accepted
time: 202ms
memory: 54504kb
input:
200000 200000 193370 156594 178879 169822 188485 49555 142167 113607 88543 91370 40082 24702 170176 143197 86037 136335 124788 149914 127229 87267 56608 83528 54838 83090 135859 139657 71089 107918 132095 199626 65995 188324 164045 77933 65075 12184 192474 126503 8110 101059 124667 84142 144586 1042...
output:
5521214211 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105...
result:
ok single line: '5521214211 105092868359 105092...8359 105092868359 105092868359 '
Test #30:
score: 37
Accepted
time: 254ms
memory: 54116kb
input:
200000 200000 124940 156594 150898 169822 16843 49555 38352 113607 177800 91370 190376 24702 170176 181656 86037 153338 124788 82735 127229 136824 148943 83528 165182 83090 94542 139657 37761 107918 132095 150016 65995 170354 164045 69243 65075 167584 81106 126503 111084 101059 124667 46920 144586 1...
output:
105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105090261188 105092868359 105092868359 105092868359 105086313349 105092868359 105092868359 105092868359 105080234487 105091936202 105092868359 105090881282 105092868359 105092868359 105092868359 105092868359 105092868359 1...
result:
ok single line: '105092868359 105092868359 1050...8359 105092868359 105092868359 '
Test #31:
score: 37
Accepted
time: 306ms
memory: 52220kb
input:
200000 200000 2382 67359 184783 147684 194742 6889 154544 56247 33501 175826 20450 139236 56282 59860 168083 23148 70858 188718 39400 77559 34418 141255 46371 103684 9681 72544 22484 52567 168483 79774 129650 46603 125504 91822 90232 141158 146652 97780 111099 107221 144112 57276 81652 141625 16641 ...
output:
104912193174 104912193174 104912193174 104910164152 104912193174 104912193174 104912193174 104912193174 104910113995 104912193174 104912193174 104912193174 104909695449 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104904950889 104912193174 104908934864 1...
result:
ok single line: '104912193174 104912193174 1049...4372 104912193174 104912193174 '
Test #32:
score: 37
Accepted
time: 352ms
memory: 54624kb
input:
200000 200000 102963 126068 196536 126498 143836 13714 133782 173153 49821 74098 61191 110127 106287 150498 103451 135215 160851 61335 171988 21851 156996 20834 178540 165694 76997 140239 49998 199546 110790 84229 73215 175160 19332 82354 72674 142705 127832 168459 168180 174308 181332 9967 148621 1...
output:
105069892770 105069892770 105069892770 105069626146 105069892770 105069050043 105069892770 105069892770 105069892770 105069892770 105061787453 105069892770 105069892770 105069892770 105063663105 105069892770 105061244203 105064688734 105069892770 105069892770 105069892770 105058259891 105069892770 1...
result:
ok single line: '105069892770 105069892770 1050...2770 105069892770 105069892770 '
Test #33:
score: 37
Accepted
time: 201ms
memory: 58752kb
input:
200000 200000 2984 112164 89186 30161 99278 45225 123287 10545 69545 96049 181936 139180 139087 137570 47847 1962 198021 39840 12981 127344 129981 190375 9908 198300 94711 57785 181076 1 101357 21405 16248 3533 8653 147103 29771 138893 13030 126155 1 186376 44455 97077 166321 92896 44593 79318 10132...
output:
3833363 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049...
result:
ok single line: '3833363 105049835405 105049835...5405 105049835405 105049835405 '
Test #34:
score: 37
Accepted
time: 326ms
memory: 48248kb
input:
200000 200000 125785 175021 121216 174698 56177 99097 15000 103049 40120 26631 18900 1479 162976 56979 150160 101651 72559 33974 16349 165896 107535 50523 49769 150648 138388 186993 181343 152547 107356 117384 195758 4020 146299 14233 15901 30387 16643 79410 91097 146119 126668 191702 183335 53737 3...
output:
50750552 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 10513...
result:
ok single line: '50750552 105133456481 10513345...6481 105133456481 105133456481 '
Extra Test:
score: 0
Extra Test Passed