QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121350 | #4839. Smaller LCA | memset0 | TL | 1906ms | 91704kb | C++20 | 8.1kb | 2023-07-07 23:54:06 | 2023-07-07 23:54:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
int n, rt, all, tot, tim, fa[N], siz[N], mxp[N], dfn[N], ans[N];
bool vis[N];
vector<int> G[N], d[N];
vector<tuple<int, int, int, int>> qry;
namespace ini {
int tot, fa[N], dfn[N], siz[N];
long long sum, pre[N];
void dfs(int u) {
dfn[u] = ++tot;
siz[u] = 1;
for (int v : G[u])
if (v != fa[u]) {
fa[v] = u;
dfs(v);
siz[u] += siz[v];
}
}
void push(int u, int x) {
pre[dfn[u]] += x;
pre[dfn[u] + 1] -= x;
}
void push(int u, int v, int x) {
if (v == fa[u]) {
pre[0] += x;
pre[dfn[u]] -= x;
pre[dfn[u] + siz[u]] += x;
} else {
pre[dfn[v]] += x;
pre[dfn[v] + siz[v]] -= x;
}
}
inline void push(int u, int v, int w, int x) {
// fprintf(stderr, "push %d %d %d : %d\n", u, v, w, x);
pre[0] += x;
push(u, v, -x);
// for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
push(u, w, -x);
// for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
}
void init() {
dfs(1);
// for (int i = 1; i <= n; i++) cerr << dfn[i] << " \n"[i == n];
// for (int i = 1; i <= n; i++) cerr << siz[i] << " \n"[i == n];
}
void solve() {
// for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];
// for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
for (int i = 1; i <= n; i++) ans[i] += pre[dfn[i]];
}
} // namespace ini
struct CountNode {
int mx, my, tim, s[N << 1];
vector<int> ans, valx, valy;
vector<pair<int, int>> nod;
vector<tuple<int, int, int>> qry;
inline void add(int k) {
for (; k <= my; k += k & -k) s[k]++;
}
inline void ask(int k, int &x) {
for (; k; k -= k & -k) x += s[k];
}
inline void addNode(int x, int y) {
// cerr << "counter::addNode " << x << " " << y << endl;
nod.emplace_back(x, y);
}
inline void addQuery(int x, int y) {
// cerr << "counter::addQuery " << x << " " << y << endl;
qry.emplace_back(x, y, qry.size());
}
inline int getQuery() {
// cerr << "counter::getQuery " << ans[tim] << endl;
return ans[tim++];
}
void init() {
// cerr << "counter::init" << endl;
tim = 0, nod.clear(), qry.clear();
}
void solve() {
ans.resize(qry.size());
fill(ans.begin(), ans.end(), 0);
if (!nod.size() || !qry.size()) return;
if (nod.size() < 5) {
for (auto &[xx, yy] : nod) {
for (auto &[x, y, i] : qry) {
if (xx <= x && yy <= y) ans[i]++;
}
}
return;
}
cerr << "counter::solve " << nod.size() << " " << qry.size() << endl;
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
if (false && nod.size() + qry.size() < n) {
valx.clear(), valy.clear();
for (auto &[x, y] : nod) {
valx.push_back(x);
valy.push_back(y);
}
for (auto &[x, y, i] : qry) {
valx.push_back(x);
valy.push_back(y);
}
sort(valx.begin(), valx.end());
sort(valy.begin(), valy.end());
valx.erase(unique(valx.begin(), valx.end()), valx.end()), mx = valx.size();
valy.erase(unique(valy.begin(), valy.end()), valy.end()), my = valy.size();
for (auto &[x, y] : nod) {
x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
y = lower_bound(valy.begin(), valy.end(), y) - valy.begin() + 1;
// cerr << "node " << x << " " << y << endl;
}
for (auto &[x, y, i] : qry) {
x = upper_bound(valx.begin(), valx.end(), x) - valx.begin();
y = upper_bound(valy.begin(), valy.end(), y) - valy.begin();
// cerr << "query " << x << " " << y << " " << i << endl;
}
} else {
mx = my = n;
}
fill(s, s + my + 1, 0);
sort(nod.begin(), nod.end());
sort(qry.begin(), qry.end());
int i = 0, j = 0;
for (int x = 1; x <= mx; x++) {
while (i < nod.size() && nod[i].first == x) {
add(nod[i].second), i++;
}
while (j < qry.size() && get<0>(qry[j]) == x) {
ask(get<1>(qry[j]), ans[get<2>(qry[j])]), j++;
}
}
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
}
} counter;
void getroot(int u) {
siz[u] = 1, mxp[u] = 0;
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
fa[v] = u;
getroot(v);
siz[u] += siz[v];
mxp[u] = max(mxp[u], siz[v]);
}
mxp[u] = max(mxp[u], all - siz[u]);
if (!rt || mxp[u] < mxp[rt]) rt = u;
}
void getnode(int u, vector<int> &cur) {
// cerr << "get node " << u << endl;
cur.push_back(u);
dfn[u] = ++tot, siz[u] = 1;
for (int v : G[u]) {
if (!vis[v] && v != fa[u]) {
fa[v] = u;
getnode(v, cur);
siz[u] += siz[v];
}
}
}
void getquery(int u) {
// cerr << "get query " << u << endl;
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
counter.addQuery(dfn[v] + siz[v] - 1, u - 1);
counter.addQuery(dfn[v] - 1, u - 1);
getquery(v);
}
}
void pushans(int u) {
// cerr << "push ans " << u << " " << w << " " << tot << endl;
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
int cur = counter.getQuery();
cur -= counter.getQuery();
ini::push(u, v, fa[u], cur);
pushans(v);
}
}
vector<pair<int, int>> mergeSort(const vector<pair<int, int>> &a, const vector<pair<int, int>> &b) {
vector<pair<int, int>> c;
int i = 0, j = 0;
while (i < a.size() && j < b.size())
if (a[i].first < b[j].first) {
c.push_back(a[i++]);
} else {
c.push_back(b[j++]);
}
while (i < a.size()) c.push_back(a[i++]);
while (j < b.size()) c.push_back(b[j++]);
return c;
}
void solve(int u) {
// cerr << "=== solve " << u << " ===" << endl;
vis[u] = 1;
vector<int> ch;
tot = 1, dfn[u] = siz[u] = 1;
for (int v : G[u]) {
if (!vis[v]) ch.push_back(v);
}
counter.init();
for (int k = 0; k < ch.size(); k++) {
int v = ch[k];
fa[v] = u;
d[k].clear(), getnode(v, d[k]);
siz[u] += siz[v];
}
vector<pair<int, int>> dx;
for (int i = 0; i < ch.size(); i++) {
sort(d[i].begin(), d[i].end());
for (int x : d[i])
if ((long long)x * u < n) {
counter.addNode(dfn[x], x * u);
} else {
break;
}
for (int x : d[i]) {
for (auto &[y, j] : dx)
if ((long long)x * y < n) {
counter.addNode(dfn[x], x * y);
counter.addNode(dfn[y], x * y);
// fprintf(stderr, "%d %d %d %d\n", x, i, y, j);
if ((long long)x * y < u) {
ini::push(u, ch[i], ch[j], 1);
}
} else {
break;
}
}
vector<pair<int, int>> di;
for (int x : d[i]) di.emplace_back(x, i);
dx = mergeSort(dx, di);
}
qry.clear(), tim = 0;
for (int v : ch) getquery(v);
counter.solve();
for (int v : ch) pushans(v);
// cerr << tim << " " << qry.size() << endl;
for (int v : ch) {
rt = 0, all = siz[v], getroot(v), solve(rt);
}
}
int main() {
#ifdef memset0
// freopen("1.in", "r", stdin);
freopen("2.in", "r", stdin);
freopen("2.out", "w", stdout);
#endif
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int u, v, i = 1; i < n; i++) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
ini::init();
rt = 0, all = n, getroot(1), solve(rt);
ini::solve();
long long tot = (long long)n * (n - 1) / 2 + n;
// for (int i = 1; i <= n; i++) cerr << ans[i] << " \n"[i == n];
for (int i = 1; i <= n; i++) cout << (tot - ans[i]) << '\n';
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
}
/*
=== solve 5 ===
counter::addNode 3 5
counter::addNode 5 2
counter::addNode 3 2
=== solve 1 ===
counter::addNode 3 4
=== solve 6 ===
=== solve 4 ===
=== solve 3 ===
=== solve 2 ===
21
21
21
20
20
21
time: 0.021
=== solve 5 ===
counter::addNode 3 5
counter::addNode 5 2
counter::addNode 3 2
counter::addNode 6 3
counter::addNode 3 3
counter::solve 5 6
=== solve 1 ===
counter::addNode 3 4
=== solve 6 ===
=== solve 4 ===
=== solve 3 ===
=== solve 2 ===
21
21
21
19
19
21
time: 0.018
*/
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 30312kb
input:
5 1 2 4 2 2 5 3 5
output:
15 15 15 15 14
result:
ok 5 number(s): "15 15 15 15 14"
Test #2:
score: 0
Accepted
time: 1315ms
memory: 87944kb
input:
300000 40632 143306 32259 40632 225153 143306 269774 225153 289668 40632 191636 269774 85717 191636 58564 191636 156509 143306 289939 40632 247103 269774 40257 40632 98149 289668 142277 143306 291616 40257 46813 225153 56324 143306 277154 142277 53903 289668 114266 32259 152231 58564 241151 152231 4...
output:
44999437117 44999604051 44999615557 44999614574 44999052534 44999484860 44999371316 44999125588 44999026878 44999118903 44999600090 44999126307 44999249359 44999307961 44999422135 44999360213 44999109672 44999283107 44999293969 44999113471 44999549862 44999278828 44999353626 44999122409 44999352565 ...
result:
ok 300000 numbers
Test #3:
score: 0
Accepted
time: 1251ms
memory: 91704kb
input:
299999 97687 248627 80337 97687 77032 80337 92616 80337 106631 248627 248726 77032 176093 92616 73262 248726 233147 80337 39942 248726 15921 176093 188366 248627 31058 80337 239076 73262 44766 233147 10344 176093 192127 233147 109285 80337 6814 176093 239926 97687 204083 77032 252211 15921 5158 7703...
output:
44999344660 44999363522 44999206495 44999093451 44999362732 44999276207 44999352410 44999343961 44999149170 44999277616 44999158043 44999332131 44999288440 44999317886 44999301651 44999266803 44999346932 44999241092 44999298075 44999129430 44999277318 44999272323 44999209973 44999271917 44999269931 ...
result:
ok 299999 numbers
Test #4:
score: 0
Accepted
time: 1316ms
memory: 91556kb
input:
300000 282498 119808 46316 119808 58818 119808 179940 119808 6601 282498 16229 46316 25007 58818 180795 16229 83945 179940 246574 179940 268478 179940 134193 246574 164637 6601 78275 83945 241804 119808 177735 6601 225133 134193 188943 179940 36121 188943 148019 164637 223449 180795 41835 188943 237...
output:
44999540514 44999412634 44999309802 44999471134 44999211366 44999458009 44999479974 44999281366 44999372403 44999448719 44999365824 44999443217 44999455734 44999482977 44999585712 44999540082 44999475151 44999453573 44999399100 44999346705 44999372230 44999256996 44999368064 44999452600 44999473178 ...
result:
ok 300000 numbers
Test #5:
score: 0
Accepted
time: 1265ms
memory: 87664kb
input:
299999 173205 142232 104374 142232 39513 104374 67867 104374 42519 173205 145713 39513 190264 104374 240190 67867 220708 240190 237545 67867 211015 220708 73889 39513 126319 220708 38274 67867 257538 240190 260471 237545 44453 142232 24527 142232 23487 173205 174569 173205 158023 173205 100347 42519...
output:
44999145790 44999091319 44999049858 44999174810 44998980768 44999252786 44999144473 44998983973 44998953014 44999259775 44998949495 44999055625 44998909201 44998956878 44999261370 44998927703 44999167393 44999140464 44998905939 44998940216 44998919447 44999239170 44999100182 44998941726 44999273329 ...
result:
ok 299999 numbers
Test #6:
score: 0
Accepted
time: 1281ms
memory: 89884kb
input:
299999 144140 64463 84381 64463 275996 144140 144612 144140 22940 275996 97432 275996 258170 64463 268975 84381 113121 268975 74024 258170 162810 275996 222898 74024 218308 22940 294515 64463 4344 218308 287764 74024 73585 97432 116481 287764 204008 144140 125526 73585 133816 294515 31053 258170 107...
output:
44999005167 44999209294 44998941343 44998935023 44999171993 44999086771 44999206524 44999091272 44998923732 44999092407 44999090745 44998910337 44998836857 44999087877 44999105320 44998879519 44998983003 44998798532 44998760921 44999084330 44999064280 44999054760 44999103030 44999130090 44999053488 ...
result:
ok 299999 numbers
Test #7:
score: 0
Accepted
time: 1866ms
memory: 89868kb
input:
300000 17050 75638 59628 17050 250487 75638 222372 17050 83877 75638 252612 59628 223823 83877 71675 252612 264309 223823 56862 222372 250608 83877 112630 223823 122103 250608 148130 56862 32428 112630 181607 56862 230036 148130 99321 230036 211188 181607 272235 148130 57324 272235 260876 272235 191...
output:
44999618044 44999147094 44999677093 44999732634 44999460409 44999160790 44999579139 44999467908 44999184681 44999199263 44999231239 44999488195 44999805266 44999547232 44999707240 44999537930 44999505219 44999563833 44999465777 44999426341 44999557653 44999794024 44999548625 44999794023 44999570124 ...
result:
ok 300000 numbers
Test #8:
score: 0
Accepted
time: 1872ms
memory: 87524kb
input:
299999 221069 282534 214173 282534 24237 221069 204787 282534 245620 204787 136288 221069 209773 245620 287963 245620 292336 24237 21383 292336 172534 209773 127524 209773 16214 21383 87226 287963 170040 172534 103312 87226 52385 127524 140929 170040 193496 52385 203825 87226 115524 170040 220799 52...
output:
44999572210 44999458670 44998911277 44999184039 44999206776 44999443592 44999417299 44999356502 44999179829 44999237265 44999572056 44999206883 44998942302 44999260955 44998835660 44999452577 44999346141 44999194483 44999380831 44998863337 44998893184 44999520307 44999572157 44999173592 44999110483 ...
result:
ok 299999 numbers
Test #9:
score: 0
Accepted
time: 1851ms
memory: 88308kb
input:
300000 8889 36706 157543 8889 104012 8889 62314 157543 242859 36706 149378 8889 10456 157543 29565 104012 131101 149378 22513 131101 90461 22513 40078 131101 141748 10456 72882 22513 176272 22513 90154 141748 215195 90154 43336 40078 296478 90154 128801 90154 149034 128801 102954 149034 254677 29647...
output:
44999724123 44999887080 44999879556 44999518077 44999609913 44999556275 44999588000 44999593838 44999680913 44999380889 44999880288 44999657021 44999383706 44999144202 44999478288 44999199032 44999614075 44999790343 44999766790 44999445094 44999424718 44999260077 44999887302 44999847443 44999676358 ...
result:
ok 300000 numbers
Test #10:
score: 0
Accepted
time: 1904ms
memory: 89740kb
input:
299998 29430 279377 87865 279377 33400 87865 149559 33400 218448 149559 274422 87865 62550 149559 215553 274422 239913 274422 107224 149559 289982 218448 256498 239913 143232 239913 103543 289982 90558 107224 254844 143232 7345 90558 139410 143232 171957 90558 85463 139410 207261 171957 128676 13941...
output:
44998919397 44998530568 44998745272 44999059683 44999013065 44999181214 44999129502 44999154742 44999172744 44998691167 44998858765 44999070146 44998807013 44998859372 44998761740 44999120708 44998877194 44998808804 44998912953 44998550644 44999009720 44998818725 44999061235 44998695918 44999085009 ...
result:
ok 299998 numbers
Test #11:
score: 0
Accepted
time: 1906ms
memory: 90372kb
input:
299999 279808 219366 64566 279808 294679 64566 192527 294679 290866 294679 282142 64566 112420 290866 29858 290866 269073 112420 19694 112420 66844 19694 42940 112420 142231 112420 58837 142231 295419 58837 9002 19694 4808 142231 7272 9002 30675 4808 62872 30675 81916 7272 260542 62872 146224 62872 ...
output:
44999374155 44999307472 44999179996 44999188269 44999102614 44999300805 44998993219 44999018542 44999252456 44999480338 44999203231 44998930625 44999347959 44999487732 44999529114 44998903631 44999333440 44999238520 44999388913 44999277968 44999288307 44998958543 44999163087 44999009462 44999226099 ...
result:
ok 299999 numbers
Test #12:
score: -100
Time Limit Exceeded
input:
299998 150616 76335 88273 150616 206635 76335 200072 206635 38950 150616 298642 206635 179779 200072 246700 38950 231698 88273 202098 76335 105468 38950 265562 38950 173901 38950 211307 200072 159253 88273 131738 150616 17278 76335 103492 76335 173877 206635 10117 38950 294264 38950 9644 206635 2619...