QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121330 | #4839. Smaller LCA | memset0 | TL | 3046ms | 159432kb | C++20 | 6.7kb | 2023-07-07 23:07:19 | 2023-07-07 23:07:20 |
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> cur, G[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 n, 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 <= n; 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);
valx.push_back(x), valy.push_back(y);
}
inline void addQuery(int x, int y) {
// cerr << "counter::addQuery " << x << " " << y << endl;
qry.emplace_back(x, y, qry.size());
valx.push_back(x), valy.push_back(y);
}
inline int getQuery() {
// cerr << "counter::getQuery " << ans[tim] << endl;
return ans[tim++];
}
void init() {
// cerr << "counter::init" << endl;
tim = 0, nod.clear(), qry.clear(), valx.clear(), valy.clear();
}
void solve() {
ans.resize(qry.size());
fill(ans.begin(), ans.end(), 0);
if (!nod.size() || !qry.size()) return;
cerr << "counter::solve " << nod.size() << " " << qry.size() << endl;
if (nod.size() < 5) {
for (auto &[xx, yy] : nod) {
for (auto &[x, y, i] : qry) {
if (xx <= x && yy <= y) ans[i]++;
}
}
return;
}
sort(valx.begin(), valx.end());
sort(valy.begin(), valy.end());
valx.erase(unique(valx.begin(), valx.end()), valx.end());
valy.erase(unique(valy.begin(), valy.end()), valy.end());
n = valy.size();
fill(s, s + n + 1, 0);
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 = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
y = lower_bound(valy.begin(), valy.end(), y) - valy.begin() + 1;
// cerr << "query " << x << " " << y << " " << i << endl;
}
sort(nod.begin(), nod.end());
sort(qry.begin(), qry.end());
int i = 0, j = 0;
for (int x = 1; x <= valx.size(); 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++;
}
}
}
} 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) {
// 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);
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);
}
}
void solve(int u) {
// cerr << "=== solve " << u << " ===" << endl;
vis[u] = 1;
vector<int> ch;
set<pair<int, int>> pre = {{u, 0}};
map<int, vector<pair<int, int>>> p;
tot = 1, dfn[u] = siz[u] = 1;
for (int v : G[u]) {
if (!vis[v]) ch.push_back(v);
}
for (int v : ch) {
fa[v] = u;
cur.clear(), getnode(v);
siz[u] += siz[v];
p[v] = {};
for (int x : cur)
for (auto &[y, w] : pre) {
if ((long long)x * y < n) {
p[v].emplace_back(x, y);
if (w) p[w].emplace_back(y, x);
if (u > (long long)x * y) {
ini::push(u, v, w, 1);
}
} else {
break;
}
}
for (int x : cur) pre.insert(make_pair(x, v));
}
qry.clear(), tim = 0;
counter.init();
for (int v : ch)
for (auto &[x, y] : p[v]) {
counter.addNode(dfn[x], x * y);
}
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);
// fprintf(stderr, "%d -> %d :: rt = %d, all = %d, mxp = %d\n", u, v, rt, all, mxp[rt]);
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];
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
for (int i = 1; i <= n; i++) cout << (tot - ans[i]) << '\n';
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 22292kb
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: 3046ms
memory: 151100kb
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: 2881ms
memory: 159216kb
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: 2866ms
memory: 159432kb
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: 2909ms
memory: 145008kb
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: 2994ms
memory: 150140kb
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: -100
Time Limit Exceeded
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...