QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121260 | #4839. Smaller LCA | memset0 | WA | 3ms | 16048kb | C++20 | 5.5kb | 2023-07-07 20:10:10 | 2023-07-07 20:10:12 |
Judging History
answer
#include <bits/stdc++.h>
#include <time.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 << 2];
vector<int> ans, val;
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);
val.push_back(x), val.push_back(y);
}
inline void addQuery(int x, int y) {
// cerr << "counter::addQuery " << x << " " << y << endl;
qry.emplace_back(x, y, qry.size());
val.push_back(x), val.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(), val.clear();
}
void solve() {
// cerr << "counter::solve" << endl;
ans.resize(qry.size());
fill(ans.begin(), ans.end(), 0);
if (!nod.size()) return;
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
n = val.size();
fill(s, s + n + 1, 0);
for (auto &[x, y] : nod) {
x = lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
y = lower_bound(val.begin(), val.end(), y) - val.begin() + 1;
}
for (auto &[x, y, i] : qry) {
x = lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
y = lower_bound(val.begin(), val.end(), y) - val.begin() + 1;
}
sort(nod.begin(), nod.end());
sort(qry.begin(), qry.end());
int i = 0, j = 0;
for (int x = 1; x <= n; 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();
for (const auto &[v, pv] : p)
for (const auto &[x, y] : pv) {
counter.addNode(dfn[x], x * y);
}
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;
}
for (int v : G[u])
if (!vis[v]) {
pushans(v, 0);
}
for (int v : G[u])
if (!vis[v]) {
rt = 0, all = siz[v], getroot(v), solve(rt);
}
}
int main() {
#ifdef memset0
freopen("A2.in", "r", stdin);
#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);
}
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;
cout << clock() / (double)CLOCKS_PER_SEC << endl;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 16048kb
input:
5 1 2 4 2 2 5 3 5
output:
15 15 15 15 14 0.003528
result:
wrong output format Expected integer, but "0.003528" found