QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121329 | #4839. Smaller LCA | memset0 | WA | 3006ms | 148208kb | C++20 | 6.7kb | 2023-07-07 23:06:24 | 2023-07-07 23:06:28 |
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() {
if (!nod.size() || !qry.size()) return;
cerr << "counter::solve " << nod.size() << " " << qry.size() << endl;
ans.resize(qry.size());
fill(ans.begin(), ans.end(), 0);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 22252kb
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: 3006ms
memory: 148208kb
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:
44999407603 44999574536 44999586043 44999585060 44999023019 44999455346 44999341802 44999096072 44998997364 44999089389 44999570576 44999096792 44999219846 44999278447 44999392621 44999330700 44999080158 44999253593 44999264466 44999083957 44999520350 44999249314 44999324112 44999092905 44999323047 ...
result:
wrong answer 1st numbers differ - expected: '44999437117', found: '44999407603'