QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#430782 | #4699. Election Campaign | Dimash# | 100 ✓ | 178ms | 44300kb | C++20 | 3.9kb | 2024-06-04 14:41:01 | 2024-06-04 14:41:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 12, MOD = 1e9 + 7;
int n,timer,tin[N],tout[N];
ll dp[N][2];
vector<int> g[N];
int up[N][20];
int b = 20;
int s[N],pos[N];
void prec(int v,int pr = -1){
s[v] = 1;
for(int &to:g[v]) {
if (to == pr) continue;
prec(to, v);
s[v] += s[to];
if (s[to] > s[g[v].front()]) {
swap(to, g[v].front());
}
}
}
int h[N],d[N],anc[N];
int _t = 1;
void prec1(int v, int pr = 0) {
if(!h[v]){
h[v] =v;
}
pos[v] = _t++;
anc[v] = pr;
// cout << v << ' ' << h[v] << ' ' << pos[v] << "x\n";
for(int to:g[v]){
if(to == pr) continue;
if(to == g[v][0]){
h[to] = h[v];
}
d[to] = d[v] + 1;
prec1(to,v);
}
}
void dfs(int v, int pr = 1) {
tin[v] = ++timer;
up[v][0] = pr;
for(int i = 1;i < b;i++){
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int to:g[v]){
if(to != pr){
dfs(to,v);
}
}
tout[v] = ++timer;
}
bool is(int x,int y){
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int lca(int v,int u){
if(is(v,u)) return v;
if(is(u,v)) return u;
for(int i = b - 1;i >= 0;i--){
if(!is(up[v][i],u)){
v = up[v][i];
}
}
return up[v][0];
}
int q;
ll res =0 ;
vector<array<int, 3>> qr[N];
ll t[N * 4];
void upd(int pos,ll val,int v = 1,int tl = 1,int tr = n){
if(tl == tr){
t[v] = val;
}else{
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos,val,v+v,tl,tm);
else upd(pos,val,v+v+1,tm+1,tr);
t[v] = t[v + v] + t[v + v + 1];
}
}
ll get(int l,int r,int v = 1,int tl = 1,int tr = n){
if(l > r || tl > r || l > tr) return 0;
if(tl >= l && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return get(l,r,v + v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
}
ll get1(int v, int u) {
if(u == -1) return 0;
ll ans = 0;
while (true) {
if (d[h[v]] < d[h[u]])
swap(v, u);
if (h[v] == h[u]) {
if (pos[v] > pos[u]) swap(v, u);
ans += get(pos[v], pos[u]);
break;
}
else {
ans += get(pos[h[v]], pos[v]);
v = anc[h[v]];
}
}
return ans;
}
void calc(int v,int pr = -1) {
for (int to: g[v]) {
if (to == pr)continue;
calc(to, v);
dp[v][0] += max(dp[to][0], dp[to][1]);
}
for (auto [x, y, c]: qr[v]) {
ll S = 0;
ll T = get(v,x) + get(v,y);
auto proc = [&](int u) {
if (u == -1) return;
while(u != v){
if(is(v,h[u])){
S += get(pos[h[u]],pos[u]);
u = anc[h[u]];
}else{
S += get(pos[v],pos[u]);
break;
}
}
};
proc(x);
proc(y);
dp[v][1] = max(dp[v][1], S + c + dp[v][0]);
}
res = max({res,dp[v][1],dp[v][0]});
upd(pos[v],dp[v][0] - max(dp[v][0],dp[v][1]));
}
void test(){
cin >> n;
for(int i = 1;i <= n - 1;i++){
int x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
prec(1);
prec1(1);
dfs(1);
cin >> q;
for(int i = 1;i <= q;i++){
int x,y,c;
cin >> x >> y >> c;
int z = lca(x, y);
if(z != x){
swap(x,y);
}
if(x == z){
qr[z].push_back({y,-1,c});
}else{
qr[z].push_back({x,y,c});
}
}
calc(1);
cout << res << '\n';
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int T = 1;
// cin >> T;
while(T--){
test();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 11768kb
input:
2 1 2 1 1 2 2288
output:
2288
result:
ok single line: '2288'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9828kb
input:
8 7 1 5 3 6 8 3 8 8 1 2 1 1 4 5 3 8 2053 6 8 853 5 8 5880 2 1 5625 6 8 8165
output:
13790
result:
ok single line: '13790'
Test #3:
score: 0
Accepted
time: 2ms
memory: 9748kb
input:
20 1 14 2 14 11 2 5 2 17 5 4 5 20 17 15 20 13 15 7 15 8 13 3 8 16 8 18 3 10 16 12 18 19 12 9 19 6 9 7 20 9 5830 16 5 8758 6 9 2098 3 13 7903 19 2 9058 10 6 9412 7 1 1481
output:
11482
result:
ok single line: '11482'
Test #4:
score: 0
Accepted
time: 2ms
memory: 11944kb
input:
1000 328 389 332 389 98 328 173 332 198 328 673 332 350 198 604 328 941 332 469 98 613 604 283 350 935 941 401 604 608 604 143 198 616 350 154 198 693 332 2 941 837 604 781 332 114 332 814 328 202 389 219 673 898 350 965 98 120 173 171 941 922 673 500 673 344 673 259 941 299 673 724 332 863 941 595 ...
output:
47601
result:
ok single line: '47601'
Test #5:
score: 0
Accepted
time: 44ms
memory: 31492kb
input:
100000 51971 1236 13827 68016 26578 66644 61123 44973 37160 47011 51357 42501 57945 42568 35192 75188 49218 81425 5377 49928 96688 45414 61479 27595 78624 46328 376 20674 89257 58214 76188 29457 74822 23279 59664 53900 40575 39255 6872 87460 97312 74452 45763 46090 23199 77843 85247 52990 24695 6709...
output:
17606
result:
ok single line: '17606'
Test #6:
score: 0
Accepted
time: 30ms
memory: 41288kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
23271
result:
ok single line: '23271'
Test #7:
score: 0
Accepted
time: 56ms
memory: 38084kb
input:
100000 45904 87322 85648 87322 30242 45904 46905 85648 75331 46905 33931 46905 74362 75331 36769 33931 22564 36769 61614 22564 5425 61614 57215 5425 35745 57215 48920 57215 55586 48920 5531 55586 51674 55586 78055 51674 57472 78055 62668 57472 35877 57472 54224 35877 35922 54224 27435 35922 27068 35...
output:
64310
result:
ok single line: '64310'
Test #8:
score: 0
Accepted
time: 40ms
memory: 28744kb
input:
100000 14607 64423 84125 14607 55044 64423 63748 84125 28264 55044 71045 64423 33239 71045 89708 55044 92999 14607 27495 33239 43851 64423 1931 28264 18907 28264 42048 64423 30029 84125 25683 84125 70650 14607 77401 89708 33562 84125 48727 84125 32618 14607 47445 33239 83172 89708 5423 84125 66176 1...
output:
20132
result:
ok single line: '20132'
Test #9:
score: 0
Accepted
time: 44ms
memory: 36048kb
input:
100000 31720 3864 84558 3864 70959 31720 31185 84558 70670 31185 87658 31185 40824 70670 55702 40824 1708 40824 33268 1708 16455 1708 73000 33268 93991 73000 99103 73000 43730 99103 29520 99103 20019 43730 78102 20019 51506 78102 86663 78102 85923 51506 72476 85923 88462 85923 30178 72476 80889 8846...
output:
20325
result:
ok single line: '20325'
Test #10:
score: 0
Accepted
time: 36ms
memory: 30568kb
input:
100000 53319 22285 2456 22285 91027 22285 12942 53319 75310 12942 80182 2456 69400 2456 66791 2456 17127 75310 39358 22285 19770 17127 81690 75310 43059 66791 55551 22285 8043 69400 93859 2456 32352 75310 11929 75310 6371 53319 67663 12942 36921 53319 91139 12942 17898 2456 52075 17127 30342 75310 1...
output:
20488
result:
ok single line: '20488'
Subtask #2:
score: 5
Accepted
Test #11:
score: 5
Accepted
time: 3ms
memory: 11928kb
input:
2 1 2 8 2 1 1 1 2 1 2 1 1 2 1 1 2 1 1 1 2 1 1 2 1 1 2 1
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 11884kb
input:
32 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 34 10 20 1 18 26 1 13 1 1 9 24 1 6 30 1 30 22 1 21 26 1 18 1 1 31 19 1 29 31 1 7 23 1 5 17 1 26 8 1 14 21 1 9 5 1 20 15 1 29 8 1...
output:
5
result:
ok single line: '5'
Test #13:
score: 0
Accepted
time: 2ms
memory: 9952kb
input:
1000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
169
result:
ok single line: '169'
Test #14:
score: 0
Accepted
time: 80ms
memory: 44196kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
346
result:
ok single line: '346'
Test #15:
score: 0
Accepted
time: 85ms
memory: 44236kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
346
result:
ok single line: '346'
Test #16:
score: 0
Accepted
time: 72ms
memory: 44300kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
15216
result:
ok single line: '15216'
Test #17:
score: 0
Accepted
time: 77ms
memory: 43944kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
357
result:
ok single line: '357'
Test #18:
score: 0
Accepted
time: 78ms
memory: 43440kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
346
result:
ok single line: '346'
Test #19:
score: 0
Accepted
time: 73ms
memory: 43548kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
15249
result:
ok single line: '15249'
Test #20:
score: 0
Accepted
time: 83ms
memory: 43912kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
347
result:
ok single line: '347'
Subtask #3:
score: 5
Accepted
Dependency #2:
100%
Accepted
Test #21:
score: 5
Accepted
time: 10ms
memory: 12536kb
input:
1000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
926532
result:
ok single line: '926532'
Test #22:
score: 0
Accepted
time: 83ms
memory: 43380kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2099103
result:
ok single line: '2099103'
Test #23:
score: 0
Accepted
time: 80ms
memory: 43292kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2156439
result:
ok single line: '2156439'
Test #24:
score: 0
Accepted
time: 70ms
memory: 43636kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
106598844
result:
ok single line: '106598844'
Test #25:
score: 0
Accepted
time: 68ms
memory: 44160kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2079103
result:
ok single line: '2079103'
Test #26:
score: 0
Accepted
time: 67ms
memory: 43776kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
106616974
result:
ok single line: '106616974'
Test #27:
score: 0
Accepted
time: 70ms
memory: 44020kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2109310
result:
ok single line: '2109310'
Test #28:
score: 0
Accepted
time: 83ms
memory: 43380kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2105146
result:
ok single line: '2105146'
Test #29:
score: 0
Accepted
time: 62ms
memory: 43708kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
106506483
result:
ok single line: '106506483'
Test #30:
score: 0
Accepted
time: 86ms
memory: 43268kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2049033
result:
ok single line: '2049033'
Subtask #4:
score: 30
Accepted
Dependency #2:
100%
Accepted
Test #31:
score: 30
Accepted
time: 174ms
memory: 35376kb
input:
100000 96035 86687 42066 92406 36849 24091 44816 45436 38792 79161 96009 9106 96280 89946 59935 35923 76476 26651 78380 81178 89300 64244 16362 8299 60889 89792 44052 8551 99879 17870 16119 70028 12516 74373 84405 45967 38404 37423 81168 12909 67350 45024 63260 85464 28025 37709 44375 405 85570 2825...
output:
275
result:
ok single line: '275'
Test #32:
score: 0
Accepted
time: 72ms
memory: 43848kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
15230
result:
ok single line: '15230'
Test #33:
score: 0
Accepted
time: 118ms
memory: 41828kb
input:
100000 14306 90001 96850 90001 54812 14306 17816 54812 28203 17816 80777 17816 97675 28203 70261 80777 45374 97675 85111 45374 91388 45374 24797 91388 30006 24797 28734 30006 67712 28734 94090 67712 47900 67712 99447 94090 52939 99447 22204 99447 26526 22204 20666 22204 21557 26526 95891 21557 44746...
output:
347
result:
ok single line: '347'
Test #34:
score: 0
Accepted
time: 86ms
memory: 32984kb
input:
100000 51619 14781 29160 51619 99690 51619 46869 29160 27825 51619 96442 46869 69910 27825 81509 51619 50468 29160 31372 27825 98430 81509 97929 27825 64063 51619 30088 96442 31140 96442 53006 50468 9369 99690 32497 46869 93796 69910 82386 51619 44161 51619 26895 99690 6929 99690 8668 27825 26282 27...
output:
10
result:
ok single line: '10'
Test #35:
score: 0
Accepted
time: 105ms
memory: 40068kb
input:
100000 20175 46088 25255 46088 29719 25255 91124 29719 92162 29719 93122 91124 81151 93122 52720 93122 63291 81151 9359 63291 88544 63291 5975 9359 14352 88544 30904 5975 51642 30904 32446 30904 56328 51642 85574 32446 54992 85574 10713 54992 27870 54992 59477 10713 95166 59477 2665 59477 10050 2665...
output:
14045
result:
ok single line: '14045'
Test #36:
score: 0
Accepted
time: 93ms
memory: 32724kb
input:
100000 93356 29339 59199 29339 31870 29339 71570 93356 67314 31870 58594 31870 89951 29339 45183 89951 85422 71570 70237 85422 66794 85422 39191 67314 17311 29339 15878 29339 71494 29339 32268 93356 43800 58594 61912 89951 14424 89951 37252 29339 25625 31870 77466 59199 85679 45183 73031 67314 53700...
output:
10
result:
ok single line: '10'
Test #37:
score: 0
Accepted
time: 125ms
memory: 41240kb
input:
100000 92907 51044 11719 51044 16905 11719 64946 16905 44155 16905 75192 64946 91112 75192 76119 91112 66289 76119 57686 76119 63644 57686 47570 63644 95391 47570 75909 47570 40280 75909 42079 75909 88511 42079 82884 88511 86052 82884 78435 86052 97079 86052 59400 78435 7679 59400 92828 7679 32014 9...
output:
350
result:
ok single line: '350'
Test #38:
score: 0
Accepted
time: 106ms
memory: 36776kb
input:
100000 49440 3692 66348 89459 1916 54001 86813 5647 40289 88497 98791 94230 57547 23396 82565 94804 78396 96656 82430 13739 78670 93012 14171 52302 58607 69861 44202 99543 7930 91462 75522 36278 8153 70057 87123 41990 31444 46962 86990 63042 39802 59927 8521 2276 37692 26176 92862 1945 74763 34455 4...
output:
21579
result:
ok single line: '21579'
Test #39:
score: 0
Accepted
time: 64ms
memory: 43424kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
15253
result:
ok single line: '15253'
Test #40:
score: 0
Accepted
time: 134ms
memory: 39360kb
input:
100000 88225 33085 31918 33085 50796 88225 71859 50796 89833 71859 8990 89833 85129 89833 28612 8990 32047 28612 49907 28612 49185 32047 87536 49185 63296 49185 19090 87536 16433 63296 35710 16433 70705 35710 4800 35710 44814 70705 76611 4800 27619 76611 85866 27619 35563 27619 46941 35563 88987 469...
output:
351
result:
ok single line: '351'
Subtask #5:
score: 10
Accepted
Test #41:
score: 10
Accepted
time: 4ms
memory: 11944kb
input:
1000 199 495 692 601 467 294 711 959 363 143 156 433 191 14 323 24 430 622 27 230 819 166 738 205 141 892 814 220 105 368 888 268 960 716 371 572 113 6 740 475 14 302 683 25 701 688 296 946 92 601 567 247 85 252 753 429 495 238 529 852 272 369 783 751 573 91 341 932 410 844 883 805 56 576 508 301 96...
output:
173613
result:
ok single line: '173613'
Test #42:
score: 0
Accepted
time: 3ms
memory: 12012kb
input:
1000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
171886
result:
ok single line: '171886'
Test #43:
score: 0
Accepted
time: 0ms
memory: 11984kb
input:
1000 413 414 917 413 313 917 622 917 75 313 530 622 364 530 859 530 392 364 312 392 340 392 445 312 549 340 891 549 477 891 495 891 827 495 122 827 70 827 18 70 556 18 362 556 426 556 863 362 560 426 275 863 998 560 427 275 50 427 527 427 802 50 858 802 604 858 403 604 447 604 231 403 135 231 52 135...
output:
1774629
result:
ok single line: '1774629'
Test #44:
score: 0
Accepted
time: 2ms
memory: 11940kb
input:
1000 704 981 447 981 329 981 781 704 320 329 783 981 293 329 769 781 653 769 758 320 371 769 957 704 174 704 515 320 396 981 843 293 914 981 578 781 956 783 390 320 344 293 212 653 412 447 40 781 506 783 441 781 639 320 632 653 223 320 778 704 865 981 331 447 698 981 501 769 883 781 767 981 616 329 ...
output:
90211
result:
ok single line: '90211'
Test #45:
score: 0
Accepted
time: 3ms
memory: 9936kb
input:
1000 883 616 149 373 533 217 551 164 380 223 226 833 48 684 387 257 466 30 208 920 227 607 129 607 643 409 796 747 648 996 412 232 355 635 685 750 709 859 442 69 414 961 646 324 725 653 768 864 803 429 134 264 98 83 815 550 146 349 317 558 889 405 729 723 561 743 622 967 27 820 114 550 390 676 424 5...
output:
187496
result:
ok single line: '187496'
Test #46:
score: 0
Accepted
time: 3ms
memory: 11948kb
input:
1000 666 416 80 666 9 666 39 9 499 39 571 499 774 571 128 571 875 774 714 128 194 714 10 194 598 10 160 598 594 160 740 594 326 740 579 326 137 326 660 137 662 137 364 660 858 364 2 858 802 2 862 2 206 862 63 862 337 206 83 63 111 337 730 83 853 111 546 853 560 853 457 546 979 560 350 457 725 979 72...
output:
1865741
result:
ok single line: '1865741'
Test #47:
score: 0
Accepted
time: 3ms
memory: 9856kb
input:
1000 718 469 977 469 898 977 89 898 558 718 155 718 895 977 412 718 604 895 76 718 149 412 146 89 198 558 442 895 941 412 371 89 724 412 842 718 126 895 919 604 418 469 957 977 945 155 249 469 700 469 132 469 102 89 278 895 633 558 737 718 360 469 484 412 152 604 693 718 376 412 912 977 708 155 780 ...
output:
93130
result:
ok single line: '93130'
Test #48:
score: 0
Accepted
time: 3ms
memory: 12076kb
input:
1000 329 905 752 905 933 752 636 933 381 636 411 381 318 381 512 411 103 318 185 512 948 103 573 948 154 948 237 573 214 154 301 214 892 301 397 301 141 397 91 397 968 91 434 91 499 968 27 434 613 499 50 613 117 50 534 50 55 117 685 55 621 685 446 621 368 621 492 368 108 492 835 492 535 835 749 535 ...
output:
202793
result:
ok single line: '202793'
Test #49:
score: 0
Accepted
time: 0ms
memory: 11996kb
input:
1000 402 779 39 779 930 779 851 779 901 930 668 930 862 39 301 779 200 901 902 901 608 779 375 402 940 39 797 39 994 668 667 851 916 301 705 402 617 901 576 39 758 779 569 39 938 851 77 779 105 301 892 930 514 668 45 39 681 301 9 862 146 930 171 402 472 200 245 301 122 901 647 39 98 901 790 301 54 4...
output:
98570
result:
ok single line: '98570'
Test #50:
score: 0
Accepted
time: 4ms
memory: 12028kb
input:
1000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
217094
result:
ok single line: '217094'
Subtask #6:
score: 40
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #51:
score: 40
Accepted
time: 124ms
memory: 31828kb
input:
100000 35149 27390 47572 65310 64516 51324 71338 4653 96666 49487 2874 93513 36642 47325 51302 69950 20515 15537 23046 13735 25034 51425 15126 31181 90454 52073 70377 66276 17624 31397 96658 42277 71778 69950 31840 52729 80410 63244 44568 92737 11653 19261 44122 14033 28974 5526 68088 789 76384 2406...
output:
145722650
result:
ok single line: '145722650'
Test #52:
score: 0
Accepted
time: 83ms
memory: 43724kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2218440
result:
ok single line: '2218440'
Test #53:
score: 0
Accepted
time: 122ms
memory: 36832kb
input:
100000 22795 92236 53498 92236 98688 22795 28534 98688 70721 28534 45461 70721 3317 45461 96843 45461 76215 96843 43315 76215 41822 43315 46452 43315 95698 41822 28882 95698 31669 28882 84937 28882 37146 84937 20933 37146 69664 20933 36745 20933 90585 36745 669 90585 6769 90585 48920 669 92230 48920...
output:
2085597
result:
ok single line: '2085597'
Test #54:
score: 0
Accepted
time: 70ms
memory: 27744kb
input:
100000 31385 57441 70135 31385 75834 57441 45258 70135 42569 31385 81730 70135 35643 57441 26846 70135 84912 31385 46768 75834 37376 75834 91073 26846 35879 75834 50048 45258 69990 81730 88984 31385 49976 75834 36177 26846 32449 31385 28980 75834 52216 81730 43126 31385 14343 45258 69342 45258 81400...
output:
99993
result:
ok single line: '99993'
Test #55:
score: 0
Accepted
time: 178ms
memory: 33788kb
input:
100000 97584 36256 8403 82091 57876 4773 63978 62385 88873 92951 70154 70421 769 70815 59156 10723 93785 99887 92531 25642 52487 87914 749 87981 32732 84578 42015 59604 95764 81705 11143 14938 84806 96857 38956 2097 62067 19147 15403 74163 47283 89322 85042 41413 71173 8934 17743 66690 19560 1274 39...
output:
1722552
result:
ok single line: '1722552'
Test #56:
score: 0
Accepted
time: 82ms
memory: 43660kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2092078
result:
ok single line: '2092078'
Test #57:
score: 0
Accepted
time: 107ms
memory: 40756kb
input:
100000 78444 51183 47120 78444 21316 47120 49557 21316 61135 49557 25798 49557 61240 25798 27378 25798 63955 27378 17718 27378 11400 63955 84780 17718 27409 84780 47919 27409 49336 47919 62162 47919 39668 49336 45052 62162 64899 39668 66455 64899 71536 64899 52193 71536 31664 71536 88489 52193 15986...
output:
99617777
result:
ok single line: '99617777'
Test #58:
score: 0
Accepted
time: 93ms
memory: 31456kb
input:
100000 26435 78303 45900 78303 94052 45900 58899 26435 29605 94052 94183 26435 31345 29605 35856 94183 56796 31345 74117 29605 50359 45900 53416 31345 44750 94183 2882 26435 65238 45900 25925 56796 95605 31345 5333 94052 22461 26435 89600 94183 32255 29605 50337 94183 29242 58899 11757 45900 59991 3...
output:
99869
result:
ok single line: '99869'
Test #59:
score: 0
Accepted
time: 120ms
memory: 37204kb
input:
100000 23992 88567 6840 14406 17638 98168 87233 52680 60830 56606 54668 82 79608 15603 79107 32028 78258 16681 58503 80170 80387 64522 86001 7375 92111 28899 27786 70653 43641 31871 28805 23862 23540 89766 46578 54694 69294 21595 81625 66566 89793 95813 89093 99397 51987 90808 68690 85719 14011 3335...
output:
145558842
result:
ok single line: '145558842'
Test #60:
score: 0
Accepted
time: 81ms
memory: 43620kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2055982
result:
ok single line: '2055982'
Test #61:
score: 0
Accepted
time: 99ms
memory: 39168kb
input:
100000 75032 83949 84641 75032 48952 84641 38727 48952 69249 48952 36300 69249 53067 36300 64124 53067 11562 64124 91858 11562 59357 11562 85297 59357 31497 59357 43786 85297 24325 43786 28239 43786 46665 24325 70674 28239 33673 46665 43005 70674 85900 43005 11623 85900 19908 11623 75659 11623 91919...
output:
100261756
result:
ok single line: '100261756'
Test #62:
score: 0
Accepted
time: 93ms
memory: 31104kb
input:
100000 64989 80332 60342 64989 75255 64989 97608 60342 96027 75255 83693 60342 81690 60342 65051 80332 29058 64989 82030 80332 64902 97608 83962 96027 44429 83693 14264 65051 66029 81690 6533 75255 34146 64989 31958 75255 53575 75255 88389 60342 37489 75255 12971 80332 38359 29058 60050 29058 22224 ...
output:
99891
result:
ok single line: '99891'
Test #63:
score: 0
Accepted
time: 151ms
memory: 33096kb
input:
100000 77461 23007 60698 4643 80045 35707 93768 37511 93060 79763 47793 26001 68753 15670 6693 82175 45200 27249 94369 73662 21704 96497 7705 75990 54750 78698 83068 13540 81380 85191 11619 26753 93847 96953 21911 39369 36266 39087 31970 23710 18223 73188 64499 69841 70287 19054 31266 51426 44012 74...
output:
1790077
result:
ok single line: '1790077'
Test #64:
score: 0
Accepted
time: 80ms
memory: 43584kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2024664
result:
ok single line: '2024664'
Test #65:
score: 0
Accepted
time: 128ms
memory: 39844kb
input:
100000 28381 53101 75838 53101 35479 28381 27576 35479 71134 35479 32120 27576 80915 32120 98385 80915 28065 98385 70317 98385 56438 70317 30127 56438 82706 30127 39344 82706 73835 39344 42457 39344 99985 73835 37955 99985 46433 99985 76156 46433 92073 46433 87709 92073 64558 87709 94864 64558 21112...
output:
2158193
result:
ok single line: '2158193'
Test #66:
score: 0
Accepted
time: 75ms
memory: 30684kb
input:
100000 23132 22273 42020 23132 1730 22273 37199 22273 25373 23132 17860 25373 32101 22273 17106 25373 82914 17106 41512 17106 66464 17860 64751 1730 50733 23132 85062 42020 16429 37199 27047 1730 54431 23132 23656 37199 61341 25373 63253 82914 93091 25373 92442 22273 15717 22273 18680 23132 98437 17...
output:
99978
result:
ok single line: '99978'
Test #67:
score: 0
Accepted
time: 174ms
memory: 32036kb
input:
100000 15200 88392 74481 29703 10118 39602 8954 73788 32902 23319 12574 84643 68951 2485 17445 48781 79403 46928 54522 86333 86120 38794 74739 85857 3199 34263 56167 94138 47932 43668 2352 76005 63481 76228 1526 99892 51191 4624 56653 23619 9892 74661 38640 85534 29929 87217 30073 93949 51152 55424 ...
output:
1708150
result:
ok single line: '1708150'
Test #68:
score: 0
Accepted
time: 68ms
memory: 43492kb
input:
100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
2090355
result:
ok single line: '2090355'
Test #69:
score: 0
Accepted
time: 106ms
memory: 40272kb
input:
100000 23104 34454 12744 34454 17033 12744 51022 17033 50831 51022 52670 50831 79666 52670 29223 52670 34878 29223 53459 34878 4376 34878 77873 53459 67374 4376 86138 67374 72688 67374 14748 72688 25069 72688 53598 25069 71158 53598 58989 71158 45373 71158 21954 58989 74176 21954 97084 21954 71107 9...
output:
100022270
result:
ok single line: '100022270'
Test #70:
score: 0
Accepted
time: 87ms
memory: 31520kb
input:
100000 47780 86334 85826 47780 75279 86334 34886 85826 28243 86334 7157 34886 52555 7157 37581 28243 23040 28243 86991 52555 52577 28243 30257 37581 69002 34886 49507 75279 52345 7157 50560 86334 32227 28243 45295 85826 95551 75279 32675 7157 36113 34886 12533 85826 30610 23040 92349 86334 77864 477...
output:
99904
result:
ok single line: '99904'
Extra Test:
score: 0
Extra Test Passed