QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#109079 | #5418. Color the Tree | shiyihangxs | WA | 561ms | 506280kb | C++14 | 2.8kb | 2023-05-27 11:40:33 | 2023-05-27 11:40:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define mpr make_pair
//mt19937_64 ra(time(0) ^ (*new char));
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
const int SIZE = 100005;
const int mod = 998244353;
int T, n;
int head[SIZE], ver[SIZE*2], nxt[SIZE*2], tot;
int rt[SIZE], tots;
ll a[SIZE];
int d[SIZE];
inline int rd(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x*f;
}
ll power(ll x, ll y){
ll jl = 1;
while(y){
if(y & 1) jl = (jl * x) % mod;
x = (x * x) % mod;
y >>= 1;
}
return jl;
}
void add(int x, int y){
ver[++tot] = y, nxt[tot] = head[x];
head[x] = tot;
}
struct Tree{
int l, r;
ll sum;
}t[SIZE*320];
void clear(int p){
t[p].l = t[p].r = t[p].sum = 0;
}
void pushup(int p){
t[p].sum = t[t[p].l].sum + t[t[p].r].sum;
}
int merge(int &x, int y, int l, int r, int now){
if(!y) return x;
if(!x) x = ++tots, clear(x);
if(l == r){
if(l-now-1 >= 0) t[x].sum += min(t[y].sum, a[l-now-1]);
// cout << l << " " << t[x].sum << endl;
return x;
}
int mid = (l + r) >> 1;
t[x].l = merge(t[x].l, t[y].l, l, mid, now);
t[x].r = merge(t[x].r, t[y].r, mid+1, r, now);
pushup(x);
return x;
}
void change(int &p, int l, int r, int x, int id){
if(!p) p = ++tots, clear(tots);
if(l == r){
if(id == 0) t[p].sum = a[id];
else t[p].sum = min(t[p].sum, a[id]);
// cout << l << " " << t[p].sum << endl;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) change(t[p].l, l, mid, x, id);
else change(t[p].r, mid+1, r, x, id);
pushup(p);
}
void ask(int p, int l, int r){
if(!p) return;
if(l == r){
t[p].sum = min(t[p].sum, a[l]);
return;
}
int mid = (l + r) >> 1;
ask(t[p].l, l, mid);
ask(t[p].r, mid+1, r);
pushup(p);
}
void dfs(int x, int fa){
for(int i = head[x]; i; i = nxt[i]){
int y = ver[i];
if(y == fa) continue;
d[y] = d[x] + 1;
dfs(y, x);
rt[x] = merge(rt[x], rt[y], 0, n-1, d[x]);
}
change(rt[x], 0, n-1, d[x], 0);
// cout << x << " " << t[rt[x]].sum << endl;
}
int main(){
T = rd();
while(T--){
tot = tots = 0;
for(int i = 1; i <= n; i++) head[i] = 0;
n = rd();
for(int i = 0; i < n; i++) a[i] = rd();
for(int i = 1; i < n; i++){
int x = rd(), y = rd();
add(x, y); add(y, x);
rt[i] = ++tots; clear(tots);
}
rt[n] = ++tots; clear(tots);
dfs(1, 0);
ask(rt[1], 0, n-1);
printf("%lld\n", t[rt[1]].sum);
}
return 0;
}
/*
3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5612kb
input:
3 4 10 15 40 1 1 2 2 3 2 4 5 10 5 1 100 1000 1 2 2 3 2 4 4 5 4 1000 200 10 8 1 2 2 3 3 4
output:
35 17 1218
result:
ok 3 number(s): "35 17 1218"
Test #2:
score: 0
Accepted
time: 21ms
memory: 5760kb
input:
3000 54 43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44 1 2 1 3 2 4 3 5 4 6 2 7 4 8 1 9 3 10 1 11 8 12 2 13 9 14 1 15 1 16 15 17 15 18 7 19 1 20 19 21 13 22 10 23 17 24 9 25 9 26 24 27 8 28...
output:
180 168 222 230 156 240 225 126 100 81 155 73 154 127 149 124 228 230 132 187 153 170 78 282 195 286 191 211 119 197 211 233 88 252 239 233 173 180 195 121 109 148 180 175 226 210 182 97 199 59 56 31 115 204 203 172 139 208 53 140 189 170 173 137 233 94 163 273 80 350 156 133 146 159 240 269 137 222...
result:
ok 3000 numbers
Test #3:
score: 0
Accepted
time: 34ms
memory: 7784kb
input:
300 474 5 24 21 41 15 23 43 48 32 19 27 40 10 49 40 6 18 41 43 31 45 18 35 36 12 10 23 45 28 23 14 43 37 45 12 16 20 17 49 13 22 8 30 19 27 40 22 14 30 47 16 39 25 48 21 26 50 8 14 26 9 30 41 15 44 24 16 46 50 39 25 47 24 45 21 18 26 21 5 39 15 10 47 48 11 44 44 33 23 14 35 39 35 30 38 9 13 15 39 5 ...
output:
329 183 264 219 323 220 348 342 410 395 80 201 299 144 207 408 360 215 283 104 320 394 277 210 273 285 242 253 265 379 360 322 202 351 195 196 266 270 171 342 239 283 286 300 331 317 345 268 173 296 275 224 480 330 264 162 199 378 254 214 231 293 229 259 241 268 380 419 233 185 364 341 328 237 320 3...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 40ms
memory: 9628kb
input:
30 4926 18 13 47 7 21 39 28 48 21 44 14 18 39 13 46 33 6 49 9 7 10 29 29 25 38 15 16 42 41 41 40 14 26 13 6 19 17 31 24 18 30 24 48 46 38 21 28 42 29 50 33 28 18 26 18 42 13 23 35 20 32 6 17 25 44 46 35 36 50 24 7 29 34 14 41 41 8 33 22 46 7 6 22 40 24 8 44 36 38 13 37 37 25 22 7 43 50 33 19 44 24 4...
output:
427 520 443 359 427 408 371 415 482 436 269 530 478 485 435 453 418 503 443 453 405 425 347 564 297 435 559 453 213 395
result:
ok 30 numbers
Test #5:
score: 0
Accepted
time: 24ms
memory: 7920kb
input:
3000 74 555233197 518812085 998593787 821753058 967306600 663279435 696954042 885219300 489323226 146136486 447383587 785317885 838306349 708275482 715157265 298848995 400280904 374077023 673881523 207667786 885945020 459791675 992519779 327830583 821713695 253985403 926395863 419409783 138881726 80...
output:
6742611216 5794349776 3087356867 4707144715 2761702533 3246645261 4802134565 2999820393 4887036613 2784978973 3593730307 4783057633 4621084176 4331196830 4242984461 2287799528 3027767371 3699192818 3888960419 6398323452 2766114996 1734720583 6543430036 1955540148 5464479116 3177069662 5145942113 302...
result:
ok 3000 numbers
Test #6:
score: 0
Accepted
time: 36ms
memory: 7808kb
input:
300 621 259262308 372414267 976777900 567821544 262206094 972740633 932600104 702535786 494092920 919901107 797100568 708295156 632473907 101958470 952065075 970482879 183543308 323078517 719011818 352232578 159576652 124505381 125133768 492132730 331846050 577415810 369370004 871034176 529186574 44...
output:
8143086197 8197999468 5370721620 5343127707 5868323006 7992625789 5749423188 5019336842 5319894438 5228239187 5391752908 6084605805 6792215852 6057910407 8471127525 2719747215 6909535671 5100581420 5878004843 5586237425 6343902433 9390109727 5651124389 5472179570 7945151774 5064107530 4433748186 571...
result:
ok 300 numbers
Test #7:
score: 0
Accepted
time: 31ms
memory: 10248kb
input:
30 5308 560111855 290003681 946208440 140658046 860834453 480249720 506770353 922783074 600720525 693059141 436061359 545671168 528534807 339705109 831632761 570564203 113225613 578123930 293066534 269996029 765346927 443717770 933144287 856263710 475170893 174188152 464281143 864607591 443380284 12...
output:
8829755982 7996435040 9259425768 7684533044 9842457103 3917213508 5939555066 8695995697 9431906955 7466353560 8322921019 8970732656 8099619221 9390765699 6773331885 8521621715 9998520099 7876760589 6482847050 10167157889 8563826262 5569616375 7783052317 7313404561 7224267995 8986870714 9082031438 99...
result:
ok 30 numbers
Test #8:
score: -100
Wrong Answer
time: 561ms
memory: 506280kb
input:
30 235 99 26 36 76 38 12 81 57 32 53 24 100 83 36 73 40 99 67 25 59 13 53 26 96 88 91 70 75 50 28 43 91 28 80 21 10 28 96 81 46 93 48 47 65 16 51 39 13 17 68 87 47 11 53 35 59 95 17 12 28 42 72 69 93 10 99 55 36 17 10 17 82 46 47 30 13 33 46 47 82 26 70 89 11 84 15 75 82 23 15 26 21 33 100 80 68 59 ...
output:
1853 53585 137553225403903979 77 16 58 90 27 25 33 18 30 76 88 80 26 15 30 32 28 58 17 73 31 69 38 17 11 25 63
result:
wrong answer 3rd numbers differ - expected: '70793', found: '137553225403903979'