QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121273 | #4839. Smaller LCA | memset0 | TL | 1ms | 16176kb | C++20 | 5.9kb | 2023-07-07 20:23:16 | 2023-07-07 20:23:18 |
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;
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() {
// cerr << "counter::solve" << endl;
ans.resize(qry.size());
fill(ans.begin(), ans.end(), 0);
if (!nod.size()) 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;
}
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;
}
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;
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, int sub) {
// cerr << "get query " << u << endl;
qry.emplace_back(dfn[u] + siz[u] - 1, u - 1, sub, 0); // plus this ans
qry.emplace_back(dfn[u] - 1, u - 1, sub, 0); // minus this ans
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
qry.emplace_back(dfn[v] + siz[v] - 1, u - 1, sub, 0); // plus this ans
qry.emplace_back(dfn[v] - 1, u - 1, sub, 0); // minus this ans
getquery(v, sub);
}
}
inline int getresult() {
int res = get<3>(qry[tim++]);
res -= get<3>(qry[tim++]);
return res;
}
void pushans(int u, int w) {
int tot = getresult();
// cerr << "push ans " << u << " " << w << " " << tot << endl;
w += tot;
ans[u] += w;
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
int sub = getresult();
pushans(v, w - sub);
}
}
void solve(int u) {
// cerr << "=== solve " << u << " ===" << endl;
vis[u] = 1;
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]) {
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[w].emplace_back(y, x);
p[v].emplace_back(x, y);
} else {
break;
}
}
for (int x : cur) pre.insert(make_pair(x, v));
}
qry.clear(), tim = 0;
for (int v : G[u])
if (!vis[v]) {
getquery(v, v);
}
counter.init();
int curans = 0;
for (const auto &[v, pv] : p)
for (const auto &[x, y] : pv) {
counter.addNode(dfn[x], x * y);
// cerr << "find " << x << " " << y << endl;
if (x < y && u > (long long)x * y) ++curans;
}
for (auto &[x, y, v, ans] : qry) {
counter.addQuery(x, y);
}
counter.solve();
for (auto &[x, y, v, ans] : qry) {
ans += counter.getQuery();
}
int i = 0, j;
for (int v : G[u])
if (!vis[v]) {
counter.init(), j = i;
while (j < qry.size() && get<2>(qry[j]) == v) {
counter.addQuery(get<0>(qry[j]), get<1>(qry[j])), j++;
}
counter.solve(), j = i;
while (j < qry.size() && get<2>(qry[j]) == v) {
get<3>(qry[j]) -= counter.getQuery(), j++;
}
i = j + 1;
}
ans[u] += curans;
for (int v : G[u])
if (!vis[v]) {
int subans = 0;
for (auto &[x, y] : p[v])
if (u > (long long)x * y) subans++;
pushans(v, curans - subans);
}
for (int v : G[u])
if (!vis[v]) {
rt = 0, all = siz[v], getroot(v), solve(rt);
}
}
int main() {
#ifdef memset0
freopen("1.in", "r", stdin);
// freopen("A2.out", "w", stdout);
#endif
ios::sync_with_stdio(0), cin.tie(0), cout.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);
}
rt = 0, all = n, getroot(1), solve(rt);
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]) << endl;
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 16176kb
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: -100
Time Limit Exceeded
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...