QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#846909 | #28. Corporate life (after hostile takover) | mnbvcxz123 | Compile Error | / | / | C++14 | 2.2kb | 2025-01-07 15:48:15 | 2025-01-07 15:48:16 |
Judging History
This is the latest submission verdict.
- [2025-01-07 15:48:16]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2025-01-07 15:48:15]
- Submitted
answer
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
int n;
std::cin >> n;
struct graph_t {
std::vector<int> dfn, siz;
std::vector<std::vector<int>> adj;
int tot;
graph_t (int n) {
dfn = std::vector<int>(n, 0);
siz = std::vector<int>(n, 1);
adj = std::vector(n, std::vector<int>());
for (int i = 1; i < n; ++i) {
int fa;
std::cin >> fa;
--fa;
adj[fa].emplace_back(i);
}
tot = 0;
auto dfs = [&](auto &self, int x) -> void {
dfn[x] = tot++;
for (int y : adj[x]) {
self(self, y);
siz[x] += siz[y];
}
};
dfs(dfs, 0);
}
} F(n), G(n);
struct query_t {
int id, x, y, coef;
query_t(int id, int x, int y, int coef) : id(id), x(x), y(y), coef(coef) {
}
bool operator<(const query_t &rhs) const {
return x < rhs.x;
}
};
struct fenwick_t {
std::vector<int> t;
static constexpr int lowbit(int x) { return x & -x; }
void add(int p, int v) {
++p;
for (; p < t.size(); p += lowbit(p))
t[p] += v;
}
int query(int p) {
++p;
int r = 0;
for (; p; p -= lowbit(p))
r += t[p];
return r;
}
fenwick_t(int n) {
t = std::vector<int>(n + 1, 0);
}
} tr(n);
std::vector<std::pair<int, int>> points;
for (int i = 0; i < n; ++i) {
points.emplace_back(F.dfn[i], G.dfn[i]);
}
std::sort(points.begin(), points.end());
std::vector<int> ans(n);
std::vector<query_t> queries;
auto add_query = [&](int id, int r1, int r2, int sgn) {
if (r1 < 0 || r2 < 0) return;
queries.emplace_back(id, r1, r2, sgn);
};
for (int i = 0; i < n; ++i) {
int l1 = F.dfn[i], r1 = F.dfn[i] + F.siz[i] - 1;
int l2 = G.dfn[i], r2 = G.dfn[i] + G.siz[i] - 1;
add_query(i, r1, r2, 1);
add_query(i, l1 - 1, r2, -1);
add_query(i, r1, l2 - 1, -1);
add_query(i, l1 - 1, l2 - 1, 1);
}
std::sort(queries.begin(), queries.end());
int p = 0;
for (auto [id, l, r, coef] : queries) {
while (p < points.size() && points[p].first <= l) {
tr.add(points[p].second, 1);
++p;
}
ans[id] += coef * tr.query(r);
}
for (int i = 0; i < n; ++i) {
std::cout << ans[i] - 1 << ' ';
}
std::cout << '\n';
}
詳細信息
answer.code: In constructor ‘main()::graph_t::graph_t(int)’: answer.code:14:42: error: missing template arguments before ‘(’ token 14 | adj = std::vector(n, std::vector<int>()); | ^ answer.code: In function ‘int main()’: answer.code:81:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 81 | for (auto [id, l, r, coef] : queries) { | ^