QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#355972 | #7305. Lowest Common Ancestor | 8BQube# | AC ✓ | 189ms | 29136kb | C++20 | 2.8kb | 2024-03-17 14:19:47 | 2024-03-17 14:19:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()
const int N = 200005;
template<class T>
struct BIT {
int n;
T bit[N], org[N];
void init(int _n) {
n = _n;
fill_n(bit + 1, n, 0);
fill_n(org + 1, n, 0);
}
void modify(int x, T v) {
for (org[x] += v; x <= n; x += x & -x)
bit[x] += v;
}
T query(int x) {
T res = 0;
for (; x; x -= x & -x)
res += bit[x];
return res;
}
};
BIT<int> counts;
BIT<ll> weighted;
struct Heavy_light_Decomposition {
int n, ulink[N], deep[N], mxson[N], w[N], pa[N];
int t, pl[N], data[N], mx[N];
vector<int> G[N];
void init(int _n) {
n = _n, t = 0;
for (int i = 1; i <= n; ++i)
G[i].clear(), mxson[i] = 0, mx[i] = 0;
}
void add_edge(int a, int b) {
G[a].pb(b);
G[b].pb(a);
}
void dfs(int u, int f, int d) {
w[u] = 1, pa[u] = f, deep[u] = d++;
for (auto &i : G[u])
if (i != f) {
dfs(i, u, d), w[u] += w[i];
if (w[mxson[u]] < w[i]) mxson[u] = i;
}
}
void cut(int u, int link) {
pl[u] = ++t, ulink[u] = link;
mx[link] = max(mx[link], pl[u]);
if (!mxson[u]) return;
cut(mxson[u], link);
for (auto i : G[u])
if (i != pa[u] && i != mxson[u])
cut(i, i);
}
void build() {
dfs(1, 0, 1);
cut(1, 1);
counts.init(n);
weighted.init(n);
}
void modify(int u) {
while (u) {
counts.modify(pl[u], 1);
weighted.modify(pl[u], data[u]);
u = pa[ulink[u]];
}
}
ll query(int u) {
ll res = 0, prv = 0;
while (u) {
int boss = ulink[u];
ll below = counts.query(mx[boss]) - counts.query(pl[u]) + counts.org[pl[u]];
res += (below - prv) * data[u];
res += weighted.query(pl[u] - 1) - weighted.query(pl[boss] - 1);
prv = counts.query(mx[boss]) - counts.query(pl[boss] - 1);
u = pa[boss];
}
return res;
}
} hld;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
while (cin >> n) {
hld.init(n);
for (int i = 1; i <= n; ++i)
cin >> hld.data[i];
for (int i = 2; i <= n; ++i) {
int p;
cin >> p;
hld.add_edge(p, i);
}
hld.build();
for (int i = 2; i <= n; ++i) {
hld.modify(i - 1);
cout << hld.query(i) << "\n";
}
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10260kb
input:
3 1 2 3 1 1 5 1 2 3 4 5 1 2 2 1
output:
1 2 1 3 5 4
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 30ms
memory: 9432kb
input:
13 887 4555 8570 5485 8611 9500 295 2499 83 4959 9772 8620 3825 4 4 1 3 7 12 2 1 9 5 8 12 16 3405 9213 9243 8188 2733 1333 1614 4907 4256 7506 4228 1286 6121 6155 4082 8084 1 12 9 4 2 13 3 8 9 7 11 15 8 1 10 5 7183 1481 9468 8242 1044 1 5 5 1 3 5758 3693 1694 1 2 20 6683 4426 5616 8166 810 4265 3000...
output:
887 6372 11857 20427 21897 22192 26895 7096 7179 47267 48895 57515 3405 6810 16053 24241 22833 15057 30886 34491 38747 37197 23773 65304 57242 55117 66877 7183 14366 15410 16454 5758 9451 6683 11109 23015 24891 29156 35244 41332 41537 37300 51071 58569 59109 70092 93562 98559 108242 88010 120021 991...
result:
ok 181926 numbers
Test #3:
score: 0
Accepted
time: 63ms
memory: 10020kb
input:
1477 3418 2604 3534 2752 131 645 5196 4830 3302 3842 1625 3740 9292 9939 1582 4155 3540 3753 7421 3629 7596 2043 1399 8955 2124 7955 6100 1346 1339 3935 767 4593 1720 3200 2248 6972 7122 9566 624 9948 6048 8338 208 8669 827 3770 4306 9503 1935 6488 454 3510 4974 2964 5407 138 5468 1142 1812 5864 803...
output:
3418 5803 9152 13820 18874 26680 33465 41014 25683 51131 42058 39772 46791 50431 71966 64478 59926 77557 63112 88734 65714 71174 94621 92142 101334 117673 92286 90454 122881 126056 126405 137417 149983 109256 150899 154398 173188 119649 166368 169452 175799 143976 216296 149549 223478 222792 195677 ...
result:
ok 199907 numbers
Test #4:
score: 0
Accepted
time: 189ms
memory: 25684kb
input:
200000 8748 791 4490 1890 3323 1988 6142 9186 1748 6247 5686 247 5513 8788 3823 7152 9488 7315 6394 4878 2869 5935 395 8470 9990 7448 3034 9602 5477 8257 9605 8576 2122 418 28 2865 6223 6295 8852 6891 1554 7663 869 728 486 5102 716 1349 82 3819 4154 9380 4368 9283 7842 4298 3903 5172 6847 2578 8050 ...
output:
8748 10980 21720 23004 28494 43086 40992 43082 51656 55659 43921 65566 70999 87217 105493 115456 108075 96154 99671 108252 123219 115979 129363 128272 161386 204287 213656 166933 194923 216010 171656 177783 187699 195840 210767 207893 227214 227883 277178 282916 225885 246528 237889 342600 263596 28...
result:
ok 199999 numbers
Test #5:
score: 0
Accepted
time: 168ms
memory: 25636kb
input:
200000 1089 2052 9819 2755 1142 9026 8106 7060 4295 7566 5317 9030 3724 3949 1766 4512 1763 4073 332 5723 9306 4271 2328 4233 9127 7407 4513 8347 5088 4319 2032 8553 5123 6344 9637 9759 639 6519 6880 6282 6297 3518 6936 1102 3337 1344 8040 3603 3866 3160 5501 7044 6637 5267 2249 7855 3766 6929 8771 ...
output:
1089 3864 8375 13838 22864 24031 18902 27077 28777 32769 38870 59226 63315 44138 57381 76962 69244 103066 99786 84003 91878 92896 102809 90402 109611 141263 139331 97590 97005 167931 143972 140174 160648 142079 192737 172340 263643 220362 218229 193811 227606 187026 202919 197660 204090 125557 17460...
result:
ok 199999 numbers
Test #6:
score: 0
Accepted
time: 174ms
memory: 25576kb
input:
200000 4960 3655 2962 5492 284 8613 2140 1855 1784 3288 6928 782 6150 919 1823 6985 4922 4588 5377 5805 3711 2564 4833 2169 5376 8179 8047 3601 3712 1133 8796 1166 6115 2174 8529 4364 2418 3091 4696 8459 5931 4623 1009 8447 6431 5783 7599 7664 3939 422 9257 9003 2591 8922 5705 2079 4434 3541 2112 75...
output:
4960 9255 15548 17532 17803 30260 61048 47274 40937 44392 101419 73337 72533 89824 79311 89089 148745 105683 103274 130544 126881 116509 115470 142269 155753 229745 158378 246875 181490 184413 169628 212405 189505 203094 210912 198270 200105 227667 222435 220034 235243 207768 363235 221680 222437 26...
result:
ok 199999 numbers
Test #7:
score: 0
Accepted
time: 152ms
memory: 25628kb
input:
200000 1992 2831 3632 5028 5398 6876 265 7751 6179 4848 9158 3408 6501 8481 7845 5506 3540 5145 4729 1886 9069 9909 1721 2476 6273 2215 5296 9017 5299 2037 9947 115 3390 5335 574 6863 5133 2156 3487 132 2673 6214 7274 6014 4223 4041 1035 4507 687 5504 3863 5873 5886 9016 9027 9926 8781 9012 4683 423...
output:
1992 10357 18862 17382 19895 47777 33964 25358 48453 32678 37540 28612 3900 70418 41017 71093 72260 88771 61948 49435 86553 57151 80177 78259 93312 108210 96451 135443 16869 129070 82621 153626 122872 135908 152350 161306 134708 105506 302147 120358 153630 164305 157384 170420 189791 45980 366067 14...
result:
ok 199999 numbers
Test #8:
score: 0
Accepted
time: 102ms
memory: 25596kb
input:
200000 8169 5022 7242 4618 3683 9870 7200 3627 4997 5129 7738 8636 2362 3814 5421 9340 4098 6699 9986 4828 1970 4295 472 3029 2832 8201 543 7008 328 134 9966 6635 2793 7159 6653 8331 6025 1272 92 6676 813 6203 475 387 6146 8771 4960 7973 4727 2154 2788 5021 384 4075 5622 6082 3605 4168 9062 6078 284...
output:
8169 10197 14815 18860 22152 30279 35393 26746 39810 43539 64870 116607 76194 66942 85971 94578 101277 97119 63371 98277 137642 134935 136332 138839 158295 76220 159301 165499 177684 180953 102367 186727 64588 193451 98503 207674 243036 217050 232352 247817 254353 240046 114336 263202 229941 207891 ...
result:
ok 199999 numbers
Test #9:
score: 0
Accepted
time: 97ms
memory: 25724kb
input:
200000 9520 6100 4800 3079 7421 5698 1679 4144 2153 6453 2237 7931 2269 2167 2262 2080 7769 818 8026 6126 7261 2021 6926 1621 2593 4739 7273 1274 8429 4995 2409 5687 5617 6929 4588 6152 2399 8220 9159 6815 764 9110 8163 2592 7459 6983 1994 1286 4689 2011 174 8588 7258 7215 2259 5813 2803 7783 6272 2...
output:
9520 19403 21411 25505 43628 57120 55647 74555 69285 90590 73265 101210 112650 117925 109693 121027 104698 156350 164376 45650 150924 166972 164579 54910 59151 184391 187351 214949 217765 209804 213313 164492 218867 210257 265240 277014 281680 237491 89810 290865 264382 294978 253891 89800 322344 33...
result:
ok 199999 numbers
Test #10:
score: 0
Accepted
time: 90ms
memory: 25960kb
input:
200000 5956 1121 8177 4202 1212 6833 6455 5492 4523 9183 4971 2644 7369 638 4808 5922 8514 4328 7020 7481 3511 7226 9369 4841 3067 4645 5637 9315 2615 9727 6106 720 4167 8768 7046 2235 1115 8918 5772 9282 8439 9409 2306 3625 9299 5367 9505 9926 9835 9425 2968 6598 9520 2972 2633 3639 1333 2650 5755 ...
output:
5956 7302 17868 23824 29780 33631 36948 57887 49575 72227 59094 72885 88452 74200 85796 92362 81412 109685 128791 103777 99159 175778 118766 137504 119447 115321 170889 131730 156998 138521 145241 131893 205196 156799 141462 166347 145696 163896 177935 162049 161747 170665 248569 183726 182658 15363...
result:
ok 199999 numbers
Test #11:
score: 0
Accepted
time: 87ms
memory: 26392kb
input:
200000 5900 5918 8506 1255 2047 8302 7821 8527 8050 8619 9309 6639 528 6501 5415 7562 4073 5905 3741 6359 6351 4647 5138 3855 9113 258 482 8192 9362 8547 3831 4076 538 2063 9605 4666 9924 3804 8047 6932 2503 2600 6255 9256 8942 4802 5090 5224 360 4879 3338 4617 7512 5622 8346 5015 8117 8725 3053 232...
output:
5900 14406 22456 28807 38808 46148 54931 62706 64932 66403 78855 80206 91707 88375 93790 127633 114372 117173 128768 137705 129909 134638 138073 183992 135106 115908 153402 187300 162257 197704 247856 186201 171567 220821 281060 177433 297637 193094 260984 259058 261658 280351 347143 296085 241406 2...
result:
ok 199999 numbers
Test #12:
score: 0
Accepted
time: 79ms
memory: 27384kb
input:
200000 4833 8709 6425 876 8669 5761 5485 8395 2650 2545 3447 6177 3503 2864 3769 9105 2618 1386 7387 6628 1099 2929 4102 8564 8470 5404 8666 3009 4213 2131 2041 2767 3892 5204 1354 6070 195 481 2711 3121 3512 176 6191 2352 2314 8298 4453 1446 8359 3596 6862 7835 1839 1017 7783 6202 2822 1413 7198 19...
output:
4833 11258 19967 19332 21982 35118 43513 34298 50891 55884 62061 62890 65381 70960 84496 93601 60820 62206 69593 62395 137204 71964 149887 162614 163761 169165 172174 175209 166930 181553 184320 187087 189854 192565 211903 202147 204877 206768 210709 214612 214901 220835 222014 224776 233074 233682 ...
result:
ok 199999 numbers
Test #13:
score: 0
Accepted
time: 66ms
memory: 29136kb
input:
200000 7320 5235 2627 4171 2297 7220 7526 2303 3596 4368 2710 1976 1897 8915 4812 1924 7019 6686 7815 8693 2689 8852 7992 5521 4479 4238 2066 4530 4970 360 9712 8550 9712 3697 3839 4704 5838 3407 7423 9717 2520 5049 5846 9777 6708 6475 8429 1856 4543 117 8289 6405 4982 5740 1779 5494 6270 6872 8361 ...
output:
7320 12555 15182 17479 24699 22073 29599 31902 34205 36915 41283 43259 45156 54071 62986 64910 71929 79744 87559 96252 98941 107793 115785 121306 134349 138587 143117 147647 152617 152977 162689 171239 179789 183486 187325 191164 197002 204425 211848 214368 221946 226995 232044 238752 245460 253889 ...
result:
ok 199999 numbers
Extra Test:
score: 0
Extra Test Passed