QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121338 | #4839. Smaller LCA | memset0 | WA | 1525ms | 73756kb | C++20 | 6.8kb | 2023-07-07 23:23:51 | 2023-07-07 23:23:53 |
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 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;
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;
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 = 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;
}
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, 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);
}
}
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];
}
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);
}
for (int x : d[i]) {
bool fl = false;
for (int j = 0; j < i; j++) {
for (int y : d[j])
if ((long long)x * y < n) {
counter.addNode(dfn[x], x * y);
counter.addNode(dfn[y], x * y);
if ((long long)x * y < u) {
ini::push(u, ch[i], ch[j], 1);
}
} else {
break;
}
}
if (!fl) break;
}
}
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);
// 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];
for (int i = 1; i <= n; i++) cout << (tot - ans[i]) << '\n';
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: 30484kb
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
Wrong Answer
time: 1525ms
memory: 73756kb
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:
45000073350 44999997735 45000006640 45000006126 44999929169 44999986535 44999948177 44999909646 44999900999 44999915136 45000000066 44999909733 44999927364 44999950832 44999967343 44999958076 44999908918 44999939786 44999935769 44999909762 44999992852 44999933641 44999954686 44999909585 44999985980 ...
result:
wrong answer 1st numbers differ - expected: '44999437117', found: '45000073350'