/**
* Description: Split tree in blocks of size sqrt(N) by introducing
* supplemental vertices. Guarantees O(sqrt(N)) for all queries.
*
* Author: Catalin Francu
**/
#include <math.h>
#include <stdio.h>
#define MAX_N 30000
#define MAX_D 20
#define NIL -1
typedef unsigned short u16;
typedef struct {
int node, next;
} cell;
cell c[3 * MAX_N];
int head[2 * MAX_N], tail[2 * MAX_N]; /* adjacency lists */
int d[2 * MAX_N]; /* vertex depths */
int p[2 * MAX_N]; /* parents */
int ba[2 * MAX_N]; /* block ancestors */
int n, supn;
int unused; /* pointer to first unused position in c */
/* Variables for cargo info. cargo[d][mod][u] stores the number of units */
/* at times of the form dk+mod for ALL vertices between u (inclusively) */
/* and the block ancestor of u (exclusively) */
int cbuffer[(MAX_D + 1) * MAX_D * MAX_N];
int *cargo[MAX_D + 1][MAX_D]; /* entry points into cbuffer */
/* precompute the (D + 1 choose 2) offsets of cargo arrays, so that we */
/* don't waste half the space */
void initCargo() {
int *ptr = cbuffer;
for (int d = 1; d <= MAX_D; d++) {
for (int i = 0; i < d; i++) {
cargo[d][i] = ptr;
ptr += 2 * n;
}
}
}
/* add v to u's adjacency list */
void addEdge(int u, int v) {
c[unused].node = v;
c[unused].next = NIL;
if (head[u] == NIL) {
head[u] = unused;
} else {
c[tail[u]].next = unused;
}
tail[u] = unused++;
}
void readTree() {
int u, v;
scanf("%d", &n);
supn = n;
for (u = 0; u < n; u++) {
head[u] = tail[u] = NIL;
}
for (int i = 0; i < n - 1; i++) {
scanf("%d%d", &u, &v);
u--; v--; /* zero-based vertices */
addEdge(u, v);
addEdge(v, u);
}
}
/* removes the child pointed at by ptr from the adjacency list of u */
void removeChild(int u, int ptr, int prev) {
if (ptr == head[u]) {
head[u] = c[ptr].next;
} else {
c[prev].next = c[ptr].next;
}
if (ptr == tail[u]) {
tail[u] = prev;
}
}
/* move u's children, up to and including ptr, to a supplemental vertex */
/* this can actually create blocks of size 2 * blockSize */
void moveChildren(int u, int ptr) {
addEdge(u, supn);
/* pointers */
head[supn] = head[u];
tail[supn] = ptr;
head[u] = c[ptr].next;
c[ptr].next = NIL;
/* depth */
d[supn] = 1 + d[u];
/* parents */
p[supn] = u;
for (int i = head[supn]; i != NIL; i = c[i].next) {
p[c[i].node] = supn;
}
supn++;
}
/* to avoid some corner cases, put a supplemental node above the root */
void fakeRoot() {
head[supn] = tail[supn] = NIL;
addEdge(supn, 0);
p[0] = supn;
p[supn] = NIL;
d[supn] = 0;
supn++;
}
/* (1) compute depths and parents */
/* (2) remove parents from neighbor lists to obtain proper child lists */
/* (3) insert vertices to split the tree into blocks of size blockSize */
/* returns the number of vertices not yet assigned to a block */
int depthDfs(int u, int parent, int depth, int blockSize) {
d[u] = depth;
p[u] = parent;
int ptr = head[u], prev = NIL, result = 0;
while (ptr != NIL && c[ptr].node < n) { /* supplementary vertices are at the end */
if (c[ptr].node == parent) {
/* remove parent from neighbor list */
removeChild(u, ptr, prev);
ptr = c[ptr].next; /* prev stays the same */
} else {
result += depthDfs(c[ptr].node, u, depth + 2, blockSize);
if (result >= blockSize) {
moveChildren(u, ptr);
prev = NIL;
ptr = head[u];
result = 0;
} else {
prev = ptr;
ptr = c[ptr].next;
}
}
}
return 1 + result; /* include u itself */
}
/* compute the block ancestor of each vertex; returns the number of
descendants not assigned to a block */
void blockAncestorDfs(int u, int ancestor) {
ba[u] = ancestor;
if (u >= n) {
ancestor = u;
}
for (int ptr = head[u]; ptr != NIL; ptr = c[ptr].next) {
blockAncestorDfs(c[ptr].node, ancestor);
}
}
int lca(int u, int v) {
/* block by block */
while (ba[u] != ba[v]) {
if (d[ba[u]] > d[ba[v]]) {
u = ba[u];
} else {
v = ba[v];
}
}
/* vertex by vertex */
while (u != v) {
if (d[u] > d[v]) {
u = p[u];
} else {
v = p[v];
}
}
/* if the LCA is a supplemental node, move above it */
return (u >= n) ? p[u] : u;
}
/* add value to cargo[dist][mod] to all the descendants of u in the same */
/* block as u */
void addTraffickerDfs(int u, int dist, int mod, int value) {
for (int j = mod; j < dist; j++) {
cargo[dist][j][u] += value;
}
if (u < n) { /* cutoff at supplemental vertices */
for (int ptr = head[u]; ptr != NIL; ptr = c[ptr].next) {
addTraffickerDfs(c[ptr].node, dist, mod, value);
}
}
}
/* Add a trafficker on the [u, v) path, where v is an ancestor of u or NIL. */
/* At vertex u the trafficker delivers at times of the form dist * k + mod. */
/* At each subsequent vertex the times are incremented by step. */
void addTraffickerPath(int u, int v, int dist, int mod, int step, int value) {
while (u != v) {
if (u < n) {
addTraffickerDfs(u, dist, mod, value);
mod += step;
}
u = p[u];
}
}
void addTrafficker(int u, int v, int value) {
int l = lca(u, v);
int dist = (d[u] + d[v] - 2 * d[l]) / 2 + 1;
addTraffickerPath(u, p[l], dist, 0, +1, value);
addTraffickerPath(v, l, dist, dist - 1, -1, value);
}
/* how many traffickers deliver goods on the path u -> root inclusively, */
/* betweeen 0 and t inclusively? */
long long countRoot(int u, int t) {
long long result = 0;
while (u != NIL) {
for (int i = 1; i <= MAX_D; i++) {
long long lo = cargo[i][t % i][u];
long long all = cargo[i][i - 1][u];
result += t / i * all + lo;
}
u = ba[u];
}
return result;
}
/* how many traffickers deliver goods on the path u -> v inclusively, */
/* betweeen 0 and t inclusively? */
long long countOrigin(int u, int v, int lca, int t) {
long long result = countRoot(u, t) + countRoot(v, t) - countRoot(lca, t);
if (lca) { /* not root */
result -= countRoot(p[lca], t);
}
return result;
}
long long countTraffickers(int u, int v, int t1, int t2) {
int l = lca(u, v);
long long result = countOrigin(u, v, l, t2);
if (t1) {
result -= countOrigin(u, v, l, t1 - 1);
}
return result;
}
int main() {
readTree();
initCargo();
int blockSize = sqrt(n) / 2; /* determined experimentally */
depthDfs(0, NIL, 1, blockSize);
fakeRoot();
blockAncestorDfs(supn - 1, NIL);
int numQueries, type, u, v, t1, t2;
/* read the initial traffickers */
scanf("%d", &numQueries);
while (numQueries--) {
scanf("%d%d", &u, &v);
addTrafficker(u - 1, v - 1, 1);
}
/* read the remaining queries */
scanf("%d", &numQueries);
while (numQueries--) {
scanf("%d%d%d", &type, &u, &v);
if (type == 1) {
addTrafficker(u - 1, v - 1, 1);
} else if (type == 2) {
addTrafficker(u - 1, v - 1, -1);
} else {
scanf("%d%d", &t1, &t2);
long long answer = countTraffickers(u - 1, v - 1, t1, t2);
printf("%lld\n", answer);
}
}
return 0;
}
Compilation message
traffickers.cpp: In function 'void readTree()':
traffickers.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
traffickers.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~
traffickers.cpp: In function 'int main()':
traffickers.cpp:271:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &numQueries);
~~~~~^~~~~~~~~~~~~~~~~~~
traffickers.cpp:273:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~
traffickers.cpp:278:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &numQueries);
~~~~~^~~~~~~~~~~~~~~~~~~
traffickers.cpp:280:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &type, &u, &v);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:286:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &t1, &t2);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2040 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
365 ms |
10232 KB |
Output is correct |
| 2 |
Correct |
353 ms |
9336 KB |
Output is correct |
| 3 |
Correct |
547 ms |
10232 KB |
Output is correct |
| 4 |
Correct |
539 ms |
10488 KB |
Output is correct |
| 5 |
Correct |
394 ms |
10232 KB |
Output is correct |
| 6 |
Correct |
507 ms |
10360 KB |
Output is correct |
| 7 |
Correct |
412 ms |
10360 KB |
Output is correct |
| 8 |
Correct |
353 ms |
10360 KB |
Output is correct |
| 9 |
Correct |
390 ms |
10484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3582 ms |
28536 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3582 ms |
29048 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3574 ms |
28920 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3574 ms |
27768 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3567 ms |
27512 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3573 ms |
29216 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3572 ms |
29560 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3576 ms |
29000 KB |
Time limit exceeded |
