QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#556873 | #6737. Neighbourhood | 251Sec | AC ✓ | 5439ms | 70388kb | C++14 | 4.6kb | 2024-09-10 21:44:54 | 2024-09-10 21:44:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 800;
struct Edge {
int v, nxt;
} e[400005];
int head[200005], len = 1;
void Insert(int u, int v) {
e[++len] = { v, head[u] };
head[u] = len;
}
int n, q;
int dpt[200005], lt[200005], rt[200005], cti, st[20][200005], prt[200005];
ll we[200005];
namespace Blk {
const int B = 500;
int bel[200005], blt[5005], brt[5005];
ll tg[5005], a[200005];
void Init() {
for (int i = 1; i <= n; i++) {
bel[i] = (i + B - 1) / B;
if (!blt[bel[i]]) blt[bel[i]] = i;
brt[bel[i]] = i;
}
}
void M(int l, int r, ll w) {
if (bel[l] == bel[r]) {
for (int i = l; i <= r; i++) a[i] += w;
}
else {
for (int i = bel[l] + 1; i < bel[r]; i++) tg[i] += w;
for (int i = l; i <= brt[bel[l]]; i++) a[i] += w;
for (int i = blt[bel[r]]; i <= r; i++) a[i] += w;
}
}
ll Q(int i) { return tg[bel[i]] + a[i]; }
void Modify(int u, ll w) { M(lt[u], rt[u], w); }
ll Query(int u) { return Q(lt[u]); }
}
void DFS(int u, int fa) {
st[0][lt[u] = ++cti] = prt[u] = fa;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == fa) continue;
dpt[i >> 1] = v;
DFS(v, u);
Blk::Modify(v, we[i >> 1]);
}
rt[u] = cti;
}
int PMin(int u, int v) { return lt[u] < lt[v] ? u : v; }
void PreST() {
for (int j = 1; j < 20; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[j][i] = PMin(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
}
int LCA(int u, int v) {
if (u == v) return u;
if ((u = lt[u]) > (v = lt[v])) swap(u, v);
int x = __lg(v - u++);
return PMin(st[x][u], st[x][v - (1 << x) + 1]);
}
int ubn[200005], dbn[200005];
vector<int> clu[200005], bn;
namespace TopCluster {
int ccl[200005], ccnt, st[200005], top;
void AddCl(int u, int v) {
if (!v) v = ccl[ccnt];
for (int i = 1; i <= ccnt; i++) {
int r = ccl[i];
ubn[r] = u, dbn[r] = v, clu[v].push_back(r);
}
ccnt = 0;
}
int wai[200005], rec[200005], ctp[200005];
void DFS(int u, int fa) {
ctp[u] = top, wai[u] = 1;
int bcnt = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == fa) continue;
st[++top] = v;
DFS(v, u);
wai[u] += wai[v];
if (rec[v]) rec[u] = rec[v], bcnt++;
}
if (wai[u] > B || bcnt > 1 || !fa) {
wai[u] = 0, rec[u] = u;
int j = ctp[u] + 1, cnt = 0, cdn = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == fa) continue;
if (cnt + wai[v] > B || (rec[v] && cdn)) {
for (; j < ctp[v] && j <= top; j++) ccl[++ccnt] = st[j];
AddCl(u, cdn), cdn = cnt = 0;
}
cnt += wai[v];
if (rec[v]) cdn = rec[v];
}
for (; j <= top; j++) ccl[++ccnt] = st[j];
if (u == 1) ccl[++ccnt] = 1;
AddCl(u, cdn);
top = ctp[u];
}
}
}
ll du[200005], dd[200005];
vector<int> pu[200005], pd[200005];
ll D(int u, int v) {
return Blk::Query(u) + Blk::Query(v) - 2 * Blk::Query(LCA(u, v));
}
void Modify(int x, ll y) {
Blk::Modify(dpt[x], y - we[x]);
we[x] = y;
int b = dbn[dpt[x]], a = ubn[b];
for (auto i : clu[b]) {
du[i] = D(i, a); dd[i] = D(i, b);
}
sort(pu[b].begin(), pu[b].end(), [](int x, int y) {
return du[x] < du[y];
});
sort(pd[b].begin(), pd[b].end(), [](int x, int y) {
return dd[x] < dd[y];
});
}
int Query(int x, ll y) {
int ans = 0;
for (auto u : clu[dbn[x]]) {
if (D(u, x) <= y) ans++;
}
for (auto u : bn) {
if (u == dbn[x]) continue;
ll da = D(ubn[u], x), db = D(u, x);
if (da < db) {
du[n + 1] = y - da;
ans += upper_bound(pu[u].begin(), pu[u].end(), n + 1, [](int x, int y) {
return du[x] < du[y];
}) - pu[u].begin();
}
else {
dd[n + 1] = y - db;
ans += upper_bound(pd[u].begin(), pd[u].end(), n + 1, [](int x, int y) {
return dd[x] < dd[y];
}) - pd[u].begin();
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &q);
Blk::Init();
for (int i = 1, u, v, w; i < n; i++) {
scanf("%d%d%d", &u, &v, &w);
Insert(u, v), Insert(v, u);
we[i] = w;
}
DFS(1, 0), PreST(), TopCluster::DFS(1, 0);
for (int i = 1; i <= n; i++) {
bn.push_back(dbn[i]);
pu[i] = pd[i] = clu[i];
}
sort(bn.begin(), bn.end());
bn.erase(unique(bn.begin(), bn.end()), bn.end());
for (int x : bn) {
int b = x, a = ubn[b];
for (auto i : clu[x]) {
du[i] = D(i, a); dd[i] = D(i, b);
}
sort(pu[b].begin(), pu[b].end(), [](int x, int y) {
return du[x] < du[y];
});
sort(pd[b].begin(), pd[b].end(), [](int x, int y) {
return dd[x] < dd[y];
});
}
while (q--) {
int op, x; ll y; scanf("%d%d%lld", &op, &x, &y);
if (op == 1) Modify(x, y);
else printf("%d\n", Query(x, y));
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 34144kb
input:
3 7 1 2 3 2 3 1 2 2 1 2 1 3 2 3 4 1 1 1 2 2 1 2 1 0 2 3 1
output:
2 2 3 3 1 2
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 3479ms
memory: 70388kb
input:
200000 200000 1 2 146181238 2 3 45037818 3 4 176924060 4 5 969365276 5 6 683948619 6 7 356268194 7 8 871634797 8 9 630254480 9 10 283061123 10 11 204904965 11 12 838381393 12 13 516373812 13 14 253862710 14 15 223572474 15 16 114452997 16 17 145251056 17 18 905638436 18 19 375445402 19 20 549829545 ...
output:
219 62303 1358 5532 65345 682 11856 120285 4980 5689 2998 2314 18102 8014 20512 2827 113022 74534 159775 14517 17961 21855 8138 265 3336 3251 7023 35187 4932 151611 14338 101 899 117 64441 888 10380 1833 29381 1014 4806 10770 23734 236 37258 2280 14550 2196 38205 80950 80839 4517 74570 13972 95914 7...
result:
ok 99572 numbers
Test #3:
score: 0
Accepted
time: 2949ms
memory: 70020kb
input:
200000 200000 1 2 656062236 2 3 261234277 3 4 723980474 4 5 755233101 5 6 542749909 6 7 9519713 7 8 878661582 8 9 402365775 9 10 9875710 10 11 894863180 11 12 4247155 12 13 287336772 13 14 76881950 14 15 132946165 15 16 174895351 16 17 93681141 17 18 504958771 18 19 372774409 19 20 406716610 20 21 2...
output:
60189 5717 13802 2030 71980 20394 75205 11241 1388 104056 11760 588 4319 49744 8187 29084 507 39561 2286 3138 42602 77393 15811 5709 15417 48109 9596 846 16875 27181 52 11525 5741 2476 34614 4877 24002 85119 171 246 19408 89 806 42261 25552 865 158 70 3444 25736 60977 4454 11905 126842 35189 3858 15...
result:
ok 180067 numbers
Test #4:
score: 0
Accepted
time: 3882ms
memory: 70256kb
input:
200000 200000 1 2 111377160 2 3 892685763 3 4 889507841 4 5 901236774 5 6 834278466 6 7 298553149 7 8 8150218 8 9 390360541 9 10 621635057 10 11 699702261 11 12 606252166 12 13 657657482 13 14 274827098 14 15 206330963 15 16 546124412 16 17 888769586 17 18 921510546 18 19 117645637 19 20 919234429 2...
output:
171 20066 102752 6642 68416 1708 644 62536 7246 7441 3463 13905 613 38743 54559 8959 4615 103272 40246 26304 149 44249 212 123 34390 82218 521 85028 17557 1014 17048 2759 3173 5518 3043 1266 22438 83793 218 27248 24662 134581 9800 16393 39893 727 13548 3 2669 26080 573 411 9172 3642 2111 19478 563 4...
result:
ok 20072 numbers
Test #5:
score: 0
Accepted
time: 5439ms
memory: 54420kb
input:
200000 200000 1 2 657504560 1 3 539914646 2 4 617534421 2 5 145385645 4 6 11287875 4 7 472341345 1 8 114534025 4 9 940656797 5 10 806152132 3 11 623707008 2 12 841303670 10 13 804880741 1 14 35219013 12 15 924229426 2 16 834808041 5 17 118952529 1 18 561626985 9 19 884416843 10 20 604788348 18 21 11...
output:
605 131 199697 199999 34 3 36514 256 21 2 261 181731 199877 199991 3229 6 122767 4374 200000 53327 40 4 7858 175711 200000 132026 169165 72 112 120267 171500 1 95691 36697 199851 200000 6940 662 200000 1 1168 2 200000 19 16 211 9 11 196444 85 42751 200000 11 200000 115222 28279 177665 691 127 197292...
result:
ok 100112 numbers
Test #6:
score: 0
Accepted
time: 4211ms
memory: 54928kb
input:
200000 200000 1 2 525193329 1 3 693042313 1 4 194485999 1 5 319160289 1 6 925926764 1 7 592828271 1 8 262594959 1 9 60806042 1 10 704487773 1 11 963570483 1 12 71530643 1 13 66914391 1 14 933028716 1 15 678371635 1 16 714555824 1 17 507124524 1 18 160041085 1 19 769379790 1 20 938594863 1 21 2405638...
output:
85288 1 28130 1 170364 1 5907 1 71883 1 184882 1 1 1 70569 200000 128205 44921 20408 1 82605 17646 1 1 1 1 22715 1 145387 1 161039 175478 1 200000 105070 1 19679 134568 200000 29028 72699 79367 1 4346 111703 200000 200000 200000 1 1 19607 49417 109205 200000 77104 200000 200000 1 1 1 200000 28475 74...
result:
ok 179761 numbers
Test #7:
score: 0
Accepted
time: 4154ms
memory: 54928kb
input:
200000 200000 1 2 796456214 2 3 740604027 3 4 363664601 4 5 815797615 5 6 463286014 6 7 430082206 7 8 639881106 8 9 14913310 9 10 887879247 10 11 796246680 11 12 802527015 12 13 437002899 13 14 281562336 14 15 688457701 15 16 905558374 16 17 617631127 17 18 193398033 18 19 642019042 19 20 610926873 ...
output:
1 94 136 110084 136 35645 135676 200000 38729 11501 9 16200 393 146 132 199986 50 10840 5194 99022 19 150100 200000 11 60695 1673 3 166621 36 98 44 7 7 200000 3055 27 65 27000 47 15214 842 1 41870 17 3213 26 175965 5 99 41 131613 199989 108859 1078 73 35 82388 34 10145 1 1 3 6 31 36 139 199995 46667...
result:
ok 100168 numbers
Test #8:
score: 0
Accepted
time: 594ms
memory: 59120kb
input:
100000 30000 1 2 232632894 2 3 615573029 3 4 812551786 4 5 161942260 5 6 457428876 6 7 89411628 7 8 402198074 8 9 266513672 9 10 866030976 10 11 357259122 11 12 903193100 12 13 702113698 13 14 49435177 14 15 402399859 15 16 280341727 16 17 222276068 17 18 8665747 18 19 33844315 19 20 112069486 20 21...
output:
21672 59783 1586 25348 1774 3133 29699 699 3686 2318 1797 5456 1494 2998 8846 4732 1492 14933 5263 37596 16672 4 8662 1768 20587 70040 100000 9272 10659 25123 16087 1168 1734 144 10726 595 5020 1771 6064 6480 40169 11797 89942 99074 19569 433 5336 764 5706 40 73256 2012 25177 57183 3743 100000 4379 ...
result:
ok 2958 numbers
Test #9:
score: 0
Accepted
time: 587ms
memory: 49004kb
input:
100000 30000 1 2 190746238 2 3 675029592 1 4 168040323 1 5 922467464 5 6 361179444 6 7 34395123 1 8 410124233 5 9 960812805 7 10 622220798 1 11 958352127 8 12 38660819 4 13 810644242 13 14 855144641 12 15 329318635 2 16 114496731 9 17 522298672 3 18 557815746 7 19 476566127 19 20 353005409 17 21 438...
output:
3327 96746 100000 100000 2 99459 25780 6 1364 3681 2 99982 21494 100000 100000 648 71 39 99579 100000 2 100000 37698 30633 312 12 29977 100000 100000 15 1 29 1926 4 100000 64460 396 100000 8099 54 511 98678 42 751 489 954 1 1 7206 178 47644 99588 3352 44594 1 100000 62862 1265 4682 412 22 26 100000 ...
result:
ok 14890 numbers
Test #10:
score: 0
Accepted
time: 417ms
memory: 49772kb
input:
100000 30000 1 2 354831917 1 3 202905598 1 4 611619647 1 5 20222478 1 6 708756128 1 7 821129867 1 8 893394198 1 9 626738967 1 10 176378473 1 11 54191181 1 12 558850835 1 13 18618138 1 14 713989739 1 15 837205587 1 16 94638856 1 17 662322139 1 18 66448477 1 19 615697398 1 20 259837281 1 21 93808179 1...
output:
1 62583 1 1 100000 93793 64328 100000 1 75867 34018 3072 1 1 91692 94061 2578 1 72165 44133 96303 1 1 100000 3013 78870 43017 87852 1 100000 46541 1 359 30700 100000 26805 1 70202 100000 100000 1 1 33742 92761 100000 55185 28767 100000 90214 100000 35616 1 100000 100000 1 1 2216 100000 15849 1 1 311...
result:
ok 26958 numbers
Test #11:
score: 0
Accepted
time: 443ms
memory: 49780kb
input:
100000 30000 1 2 104249460 2 3 478232035 3 4 466312804 4 5 189561732 5 6 362119693 6 7 53996994 7 8 566013752 8 9 731486787 9 10 923017604 10 11 520020314 11 12 598450495 12 13 772432347 13 14 65082675 14 15 905376194 15 16 112445962 16 17 449717550 17 18 624966046 18 19 300208577 19 20 198329359 20...
output:
28 7 20 155 51 24492 23685 30 133 14700 204 50775 50177 114 532 83 2884 27 20855 23 117 194 139 67820 36 31788 27 100000 142 186 4 10014 6 7942 1 100000 132 73715 10 74 160 66725 11 100000 100000 22 57463 15280 303 35136 51 65 556 113 34054 24 851 20527 1101 54 45368 3 42 702 11 35 3762 3 93588 8 58...
result:
ok 15102 numbers
Test #12:
score: 0
Accepted
time: 499ms
memory: 56772kb
input:
100000 30000 1 2 793126017 2 3 232330993 3 4 449065337 4 5 490733472 5 6 111589134 6 7 668100127 7 8 821095971 8 9 285891331 9 10 902446109 10 11 449050951 11 12 520804843 12 13 640551484 13 14 545522531 14 15 371179414 15 16 413586021 16 17 396937695 17 18 796739570 18 19 326494170 19 20 769171110 ...
output:
54598 7234 2670 42497 20235 1707 178 12828 7636 8991 100000 6821 11643 35392 52297 39388 5538 30741 524 83977 1168 58757 8619 10299 4380 7501 13833 35865 193 19087 3646 38201 123 369 100000 12576 2484 23287 95 14638 2205 19 8385 5045 11518 27273 96810 39236 31815 48670 3476 10351 23503 100000 1234 1...
result:
ok 14953 numbers
Test #13:
score: 0
Accepted
time: 349ms
memory: 60084kb
input:
100000 30000 1 2 914076278 2 3 849075708 3 4 838143543 4 5 395635779 5 6 178103168 6 7 238090750 7 8 485456169 8 9 96798738 9 10 953953655 10 11 753633712 11 12 310722446 12 13 434513796 13 14 146296271 14 15 7536252 15 16 234163959 16 17 265914804 17 18 819483810 18 19 31553002 19 20 659460957 20 2...
output:
29412 26523 56269 58437 2301 695 2265 5556 13671 5033 74 1205 2475 11967 10762 62 413 1799 47885 466 167 102 8973 83448 7401 1503 3632 199 46638 56906 27 27503 11561 25788 27150 18473 6389 3730 20391 1750 41898 2025 23885 52 2273 22550 483 31639 15507 34642 26231 11512 53564 17996 2041 14127 8179 14...
result:
ok 27055 numbers
Test #14:
score: 0
Accepted
time: 4270ms
memory: 54132kb
input:
200000 200000 1 2 462099758 1 3 866972101 2 4 996540461 2 5 578524349 3 6 571095940 3 7 703136877 4 8 666580508 4 9 285459002 5 10 814201161 5 11 660727584 6 12 654376807 6 13 837770648 7 14 714870560 7 15 104972922 8 16 32803231 8 17 735694895 9 18 110658827 9 19 889606190 10 20 17130278 10 21 4067...
output:
200000 67686 200000 200000 200000 200000 200000 630 1 200000 200000 1 31346 1 200000 200000 561 5 1 200000 200000 200000 200000 26451 200000 200000 4 200000 200000 16916 200000 200000 153875 200000 200000 200000 200000 269 25 200000 200000 200000 200000 1 5742 200000 200000 200000 113574 200000 2942...
result:
ok 100022 numbers
Test #15:
score: 0
Accepted
time: 3421ms
memory: 55580kb
input:
200000 200000 1 2 267010287 2 3 167068641 3 4 926147815 4 5 278208820 5 6 739843382 6 7 662489052 7 8 868323923 8 9 370708651 9 10 197960447 10 11 453593839 11 12 593358148 12 13 867598178 13 14 321466717 14 15 531052203 15 16 684794512 16 17 86921369 17 18 272875802 18 19 77083057 19 20 244571756 2...
output:
468 89 102 5 41 491 207 198 288 307 197 143 57 275 168 5 34 150 151 87 221 634 7 69 181 80 17 49 41 49 60 1323 1815 1179 981 28 922 234 38 124 25 459 406 1122 37 239 375 645 144 28 367 69 1168 413 33 43 305 422 26 30 2 668 2436 45 31 810 17 113 267 1 467 208 38 68 22 284 132 286 7 22 9 7 346 249 1 9...
result:
ok 99810 numbers
Test #16:
score: 0
Accepted
time: 3565ms
memory: 54464kb
input:
200000 200000 1 2 530262027 1 3 577167565 1 4 991638279 1 5 867902762 1 6 49113833 1 7 636751479 1 8 757930507 1 9 457909927 1 10 811776506 1 11 92479382 1 12 668573430 1 13 368351521 1 14 482946458 1 15 716207055 1 16 734689871 1 17 469203061 1 18 436245204 1 19 936484001 1 20 650565287 1 21 981462...
output:
543 17908 18325 96565 6039 60319 9138 32634 38869 163527 5272 67242 16885 41840 19723 40571 12028 8596 9708 671 165873 38146 17699 22998 242 24416 18562 5659 34 1 2340 91317 16323 17238 4040 98902 6897 13092 38011 12305 31218 105668 1 368 1881 11920 24287 37200 28287 18319 14607 15748 39054 49303 13...
result:
ok 99822 numbers
Test #17:
score: 0
Accepted
time: 3865ms
memory: 54468kb
input:
200000 200000 1 2 747157235 1 3 495557667 1 4 557250681 1 5 373058000 1 6 330210729 1 7 842153828 1 8 834790086 1 9 82820423 1 10 234384256 1 11 169048934 1 12 554053879 1 13 656281805 1 14 245175239 1 15 15339182 1 16 130032764 1 17 634709406 1 18 507167281 1 19 522574826 1 20 757475198 1 21 875842...
output:
19849 96 49 1 47 779 74734 110653 87 147530 12843 3 8 32643 76190 78606 27368 8535 56 3733 2420 2 42669 2746 200000 21675 18 5584 1708 2254 27 1 70122 406 203 81795 17262 61177 204 107338 80699 4146 2230 8855 3109 104314 3992 1424 399 14894 28 7 200000 39416 43093 11 20664 32 6760 57702 71 2851 82 8...
result:
ok 99760 numbers