QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121308 | #4839. Smaller LCA | memset0 | Compile Error | / | / | C++20 | 6.7kb | 2023-07-07 21:55:38 | 2023-07-07 21:55:39 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-07 21:55:39]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-07-07 21:55:38]
- 提交
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];
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;
for (int v : G[u])
if (v != fa[u]) {
fa[v] = u;
dfs(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;
}
}
void init() { dfs(1); }
void solve() {
for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];
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() {
// 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, 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, 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) {
// cerr << "push ans " << u << " " << w << " " << tot << endl;
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
int cur = getresult();
ini::pre[0] += cur;
ini::push(u, -cur);
ini::push(u, v, -cur);
ini::push(u, 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<int>> d;
map<int, vector<pair<int, int>>> p;
p[0] = {};
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;
d[v] = {};
getnode(v, d[v]);
siz[u] += siz[v];
p[v] = {};
for (int x : d[v])
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 : d[v]) pre.insert(make_pair(x, v));
}
qry.clear(), tim = 0;
for (int v : ch) getquery(v, v);
counter.init();
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) {
}
}
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 : ch) {
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 : ch) {
int subans = 0;
ini::push(u, v, curans);
for (auto &[x, y] : p[v])
if (u > (long long)x * y) subans++;
pushans(v, curans - subans);
}
for (int v : ch) {
rt = 0, all = siz[v], getroot(v), 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);
}
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]) << '\n';
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
}
Details
answer.code: In function ‘void solve(int)’: answer.code:211:13: error: ‘curans’ was not declared in this scope; did you mean ‘wctrans’? 211 | ans[u] += curans; | ^~~~~~ | wctrans