QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#430778 | #4699. Election Campaign | Dimash# | 20 | 109ms | 38096kb | C++20 | 3.9kb | 2024-06-04 14:38:12 | 2024-06-04 14:38:12 |
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;
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){
S += get(pos[u],pos[u]);
u = up[u][0];
continue;
if(is(v,h[u])){
S += get(pos[h[u]],pos[v]);
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: 11752kb
input:
2 1 2 1 1 2 2288
output:
2288
result:
ok single line: '2288'
Test #2:
score: 0
Accepted
time: 0ms
memory: 11892kb
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: 0ms
memory: 11836kb
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: 12008kb
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: 34ms
memory: 33120kb
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: 41ms
memory: 38052kb
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: 67ms
memory: 38096kb
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: 28ms
memory: 30032kb
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: 109ms
memory: 36660kb
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: 38ms
memory: 29660kb
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: 0
Time Limit Exceeded
Test #11:
score: 5
Accepted
time: 0ms
memory: 11896kb
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: 11772kb
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: 4ms
memory: 11976kb
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: -5
Time Limit Exceeded
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:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 10
Accepted
Test #41:
score: 10
Accepted
time: 0ms
memory: 13944kb
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: 12ms
memory: 12032kb
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: 3ms
memory: 11968kb
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: 11984kb
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: 4ms
memory: 12008kb
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: 12008kb
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: 11928kb
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: 12ms
memory: 12032kb
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: 3ms
memory: 12060kb
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: 11ms
memory: 12044kb
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: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%