QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105265 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | bashkort# | 0 | 720ms | 361024kb | C++20 | 5.9kb | 2023-05-13 20:13:43 | 2024-05-26 02:53:44 |
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 || lx >= r) {
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);
};
insertVertex(v);
for (int i = 1; i < adj[v].size(); ++i) {
int to = adj[v][i];
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) {
//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]) {
insertVertex(u);
}
fa[to] = v;
subQueries[v].insert(subQueries[v].end(), subQueries[to].begin(), subQueries[to].end());
subVertices[v].insert(subVertices[v].end(), subVertices[to].begin(), subVertices[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);
// cout << "born: " << j << " " << t << endl;
}
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: 6ms
memory: 29108kb
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:
49 32 47 20 33 45 42 42 58 30 25 29 56 32 48 67 41 53 64 14 45 53 46 49 21 24 48 57 20 49 37 54 43 46 33 60 47 30 21 59 53 14 25 69 55 32 44 48 22 37 20 24 28 46 50 51 19 46 33 14 52 30 47 32 52 48 17 53 26 65 55 22 38 28 20 33 45 43 71 45 51 40 35 34 69 36 34 46 19 45 16 64 63 45 9 51 65 40 72 49 1...
result:
wrong answer 1st numbers differ - expected: '3226', found: '49'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 444ms
memory: 355116kb
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:
33 50 29 64 52 16 69 82 39 46 39 53 27 25 9 49 10 42 51 11 43 50 56 40 22 7 28 33 64 63 41 20 1 5 4 3 3 7 46 88 79 68 67 26 58 70 51 29 64 42 45 11 55 46 85 44 37 32 9 17 53 23 59 43 14 40 1 14 71 60 26 29 11 27 57 55 13 13 18 38 21 71 54 49 53 19 56 20 3 60 13 9 79 62 78 5 11 12 17 38 48 27 68 5 58...
result:
wrong answer 1st numbers differ - expected: '757', found: '33'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 720ms
memory: 361024kb
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:
22 74 101 61 91 116 68 70 24 79 32 23 47 122 27 94 38 89 109 62 120 94 31 101 78 42 129 119 97 25 122 48 36 118 58 87 105 135 57 101 112 135 63 74 100 79 84 46 38 46 105 78 68 107 95 51 90 95 28 120 102 51 77 110 157 83 76 80 101 136 58 118 129 119 102 96 114 111 83 137 82 75 59 30 148 97 36 65 44 6...
result:
wrong answer 1st numbers differ - expected: '78', found: '22'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%