QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105269 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | bashkort# | 0 | 840ms | 377660kb | C++20 | 6.1kb | 2023-05-13 20:25:34 | 2024-05-26 02:53:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SegmentTree {
SegmentTree *left = nullptr, *right = nullptr;
int sum = 0, lx = 0, rx = 0;
SegmentTree(int l, int r) {
sum = 0, lx = l, rx = r;
}
void modify(int i, int d) {
sum += d;
if (lx + 1 == rx) {
return;
}
int mid = lx + rx >> 1;
if (i < mid) {
if (!left) {
left = new SegmentTree(lx, mid);
}
left->modify(i, d);
} else {
if (!right) {
right = new SegmentTree(mid, rx);
}
right->modify(i, d);
}
}
int rangeSum(int l, int r) {
if (l >= r || lx >= r || l >= rx) {
return 0;
}
if (l <= lx && rx <= r) {
return sum;
}
return (left ? left->rangeSum(l, r) : 0) + (right ? right->rangeSum(l, r) : 0);
}
};
constexpr int N = 2e5 + 1;
vector<int> adj[N], subVertices[N], dying[N];
vector<pair<int, int>> subQueries[N], born[N]; //id, 0/1
SegmentTree *V[N], *A[N], *D[N];
set<int> mda[N];
int path[N][2], type[N];
ll answer[N];
int deadDepth[N], dist[N], LCA[N];
int depth[N], jump[N], tin[N], tout[N], parent[N], n, fa[N];
int isp(int x, int y) {
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int leader(int x) {
while (x != fa[x]) {
x = fa[x] = fa[fa[x]];
}
return x;
}
void dfsInit(int v) {
static int T = 0;
tin[v] = T++;
for (int to : adj[v]) {
adj[to].erase(find(adj[to].begin(), adj[to].end(), v));
depth[to] = depth[v] + 1;
parent[to] = v;
int p = jump[v], pp = jump[p];
if (depth[pp] - depth[p] == depth[p] - depth[v]) {
jump[to] = pp;
} else {
jump[to] = v;
}
dfsInit(to);
}
tout[v] = T;
}
int lca(int x, int y) {
while (!isp(x, y)) {
if (!isp(jump[x], y)) {
x = jump[x];
} else {
x = parent[x];
}
}
return x;
}
void dfs(int v) {
for (int &to : adj[v]) {
dfs(to);
if (subQueries[to].size() + subVertices[to].size() > subQueries[adj[v][0]].size() + subVertices[adj[v][0]].size()) {
swap(adj[v][0], to);
}
}
if (!adj[v].empty()) {
int x = adj[v][0];
swap(V[v], V[x]), swap(A[v], A[x]), swap(D[v], D[x]);
swap(subQueries[v], subQueries[x]), swap(subVertices[x], subVertices[x]);
fa[x] = v;
} else {
V[v] = new SegmentTree(0, n);
A[v] = new SegmentTree(0, n);
D[v] = new SegmentTree(-n, n);
}
auto insertVertex = [&](int u) {
A[v]->modify(depth[u] - depth[v], 1);
D[v]->modify(depth[v] - (depth[u] - depth[v]), 1);
V[v]->modify(depth[u], 1);
subVertices[v].push_back(u);
};
insertVertex(v);
for (int i = 1; i < adj[v].size(); ++i) {
int to = adj[v][i];
for (int u : subVertices[to]) {
A[v]->modify(depth[u] - depth[v], 1);
D[v]->modify(depth[v] - (depth[u] - depth[v]), 1);
}
for (auto [j, t] : subQueries[to]) {
if (type[j] == 0) {
if (!isp(path[j][t ^ 1], path[j][t]) && leader(path[j][t ^ 1]) == v) {
cout << "here!" << endl;
//already added his friend
continue;
}
//alive
answer[j] += A[to]->rangeSum(0, dist[j] + 1);
answer[j] += V[v]->rangeSum(depth[v], depth[v] + dist[j] + 1);
answer[j] -= A[v]->rangeSum(0, dist[j] + 1);
} else {
//dead
answer[j] += D[to]->rangeSum(deadDepth[j], n);
answer[j] += V[v]->rangeSum(depth[v], depth[v] + (dist[j] - (depth[LCA[j]] - depth[v])) + 1);
answer[j] -= D[v]->rangeSum(deadDepth[j], n);
}
}
for (int u : subVertices[to]) {
subVertices[v].push_back(u);
V[v]->modify(depth[u], 1);
}
fa[to] = v;
subQueries[v].insert(subQueries[v].end(), subQueries[to].begin(), subQueries[to].end());
subQueries[to].clear(), subVertices[to].clear();
}
for (auto [j, t] : born[v]) {
//alive
answer[j] += V[v]->rangeSum(depth[v], depth[v] + dist[j] + 1);
answer[j] -= A[v]->rangeSum(0, dist[j] + 1);
}
subQueries[v].insert(subQueries[v].end(), born[v].begin(), born[v].end());
for (int j : dying[v]) {
answer[j] += A[v]->rangeSum(0, dist[j] + 1);
answer[j] -= D[v]->rangeSum(deadDepth[j], n);
type[j] = 1;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
iota(fa, fa + N, 0);
cin >> n;
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
a -= 1, b -= 1;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfsInit(0);
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> path[i][0] >> path[i][1] >> dist[i];
path[i][0] -= 1, path[i][1] -= 1;
LCA[i] = lca(path[i][0], path[i][1]);
deadDepth[i] = depth[LCA[i]] - dist[i];
if (isp(path[i][1], path[i][0])) {
swap(path[i][1], path[i][0]);
}
born[path[i][1]].emplace_back(i, 1);
if (!isp(path[i][0], path[i][1])) {
born[path[i][0]].emplace_back(i, 0);
}
dying[LCA[i]].push_back(i);
// cout << path[i][0] << " " << path[i][1] << " " << LCA[i] << " " << deadDepth[i] << endl;
}
dfs(0);
for (auto [j, t] : subQueries[0]) {
if (type[j] == 0) {
answer[j] += A[0]->rangeSum(0, dist[j] + 1);
} else {
answer[j] += D[0]->rangeSum(deadDepth[j], n);
}
}
for (int i = 0; i < q; ++i) {
cout << answer[i] << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 10ms
memory: 33972kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! ...
result:
wrong output format Expected integer, but "here!" found
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 597ms
memory: 371712kb
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
336 3703 629 4908 4106 99 3834 4962 1810 3048 2575 4398 139 326 14 2397 31 3553 3729 34 3766 4372 4250 823 384 51 3223 3416 4634 3838 4125 85 1 6 4 3 3 11 3394 4768 4540 4297 4448 3436 3604 4118 3997 186 4499 3680 1180 24 3835 3920 4910 3119 2113 707 29 94 2972 158 3849 1931 40 784 1 39 4722 4163 84...
result:
wrong answer 1st numbers differ - expected: '757', found: '336'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 840ms
memory: 377660kb
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! here! ...
result:
wrong output format Expected integer, but "here!" found
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%