## Submission #926314

# Submission time Handle Problem Language Result Execution time Memory
926314 2024-02-12T19:11:03 Z rainboy ROI16_sending (ROI16_sending) C
29 / 100
5000 ms 84924 KB
```#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	200000
#define M	200000
#define L	19	/* L = ceil(log2(M * 2)) */
#define N_	(M * 2 * (L + 1) + 1)
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
return (X *= 3) >> 1;
}

int *ej[N], eo[N], *eh[N], eo_[N], n;

void append(int **ej, int *eo, int i, int j) {
int o = eo[i]++;

if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}

int dd[N], pp[N], qq[N], ta[N], tb[N];

int dfs1(int i, int d) {
int o, s, k_, j_;

dd[i] = d;
s = 1, k_ = 0, j_ = -1;
for (o = eo[i]; o--; ) {
int j = ej[i][o], k = dfs1(j, d + 1);

s += k;
if (k_ < k)
k_ = k, j_ = j;
}
qq[i] = j_;
return s;
}

void dfs2(int i, int q) {
static int time;
int o, j_;

ta[i] = time++;
j_ = qq[i], qq[i] = q;
if (j_ != -1)
dfs2(j_, q);
for (o = eo[i]; o--; ) {
int j = ej[i][o];

if (j != j_)
dfs2(j, j);
}
tb[i] = time;
}

int lca(int i, int j) {
while (qq[i] != qq[j])
if (dd[qq[i]] > dd[qq[j]])
i = pp[qq[i]];
else
j = pp[qq[j]];
return dd[i] < dd[j] ? i : j;
}

int ii[M * 2], idx[M * 2], m;

void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

while (j < k) {
int c = ta[ii[hh[j]]] - ta[ii[h]];

if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}

int hh_[M * 2], dd1[M * 4], ddmn[M * 4];

void build(int l, int r) {
int m;

if (r - l == 1)
ddmn[l + r] = INF;
else {
m = (l + r) / 2;
build(l, m), build(m, r);
ddmn[l + r] = min(min(ddmn[l + m], dd1[m]), ddmn[m + r]);
}
}

int ll[N_], rr[N_], ddp[N_], ddq[N_], ddmx[N_];

int node(int l, int r, int i) {
static int _ = 1;
int t = _++;

if (r - l == 1)
ddp[t] = ddq[t] = INF, ddmx[t] = -1;
else {
int m = (l + r) / 2;

if (i < m) {
ll[t] = node(l, m, i);
ddp[t] = ddp[ll[t]], ddq[t] = min(min(ddq[ll[t]], dd1[m]), ddmn[m + r]);
} else {
rr[t] = node(m, r, i);
ddp[t] = min(min(ddmn[l + m], dd1[m]), ddp[rr[t]]), ddq[t] = ddq[rr[t]];
}
ddmx[t] = -1;
}
return t;
}

int remove_(int t, int l, int r, int i) {
if (r - l == 1)
t = 0;
else {
int m = (l + r) / 2;

if (i < m)
ll[t] = remove_(ll[t], l, m, i);
else
rr[t] = remove_(rr[t], m, r, i);
if (ll[t] == 0 && rr[t] == 0)
t = 0;
else {
ddp[t] = ll[t] ? ddp[ll[t]] : min(min(ddmn[l + m], dd1[m]), ddp[rr[t]]);
ddq[t] = rr[t] ? ddq[rr[t]] : min(min(ddq[ll[t]], dd1[m]), ddmn[m + r]);
ddmx[t] = max(max(ddmx[ll[t]], ddmx[rr[t]]), min(min(ddq[ll[t]], dd1[m]), ddp[rr[t]]));
}
}
return t;
}

int merge(int t1, int t2, int l, int r) {
int m;

if (t1 == 0)
return t2;
if (t2 == 0)
return t1;
m = (l + r) / 2;
ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r);
ddp[t1] = ll[t1] ? ddp[ll[t1]] : min(min(ddmn[l + m], dd1[m]), ddp[rr[t1]]);
ddq[t1] = rr[t1] ? ddq[rr[t1]] : min(min(ddq[ll[t1]], dd1[m]), ddmn[m + r]);
ddmx[t1] = max(max(ddmx[ll[t1]], ddmx[rr[t1]]), min(min(ddq[ll[t1]], dd1[m]), ddp[rr[t1]]));
return t1;
}

int find_p(int t, int l, int r) {
int m;

if (r - l == 1)
return hh_[l] >> 1;
m = (l + r) / 2;
return ll[t] ? find_p(ll[t], l, m) : find_p(rr[t], m, r);
}

int find_q(int t, int l, int r) {
int m;

if (r - l == 1)
return hh_[l] >> 1;
m = (l + r) / 2;
return rr[t] ? find_q(rr[t], m, r) : find_q(ll[t], l, m);
}

void find_mx(int t, int l, int r, int *h1, int *h2) {
int m;

assert(r - l > 1);
m = (l + r) / 2;
if (ddmx[ll[t]] == ddmx[t])
find_mx(ll[t], l, m, h1, h2);
else if (ddmx[rr[t]] == ddmx[t])
find_mx(rr[t], m, r, h1, h2);
else
*h1 = find_q(ll[t], l, m), *h2 = find_p(rr[t], m, r);
}

int t_, d_, h1_, h2_;

void dfs3(int i) {
static int hh[M * 2], tt[M * 2], dd1[M * 2];
int m_, cnt, h, o, d, d1;

m_ = 0;
for (o = eo_[i]; o--; ) {
h = eh[i][o];
hh[m_++] = h << 1 | 0, hh[m_++] = h << 1 | 1;
}
sort(hh, 0, m_);
cnt = 0;
for (h = 0; h <= m_; h++) {
d1 = h == 0 || h == m_ ? -1 : dd[lca(ii[hh[h]], ii[hh[h - 1]])];
while (cnt >= 2 && dd1[cnt - 1] >= d1) {
tt[cnt - 2] = merge(tt[cnt - 2], tt[cnt - 1], 0, m * 2);
if (ddmx[tt[cnt - 2]] != -1) {
d = dd1[cnt - 1] + ddmx[tt[cnt - 2]] - dd[i] * 2;
if (d_ < d)
d_ = d, find_mx(tt[cnt - 2], 0, m * 2, &h1_, &h2_);
}
cnt--;
}
if (h < m_)
tt[cnt] = node(0, m * 2, idx[hh[h] ^ 1]), dd1[cnt] = d1, cnt++;
}
t_ = merge(t_, tt[0], 0, m * 2);
if (ddmx[t_] != -1) {
d = ddmx[t_] - dd[i];
if (d_ < d)
d_ = d, find_mx(t_, 0, m * 2, &h1_, &h2_);
}
for (o = eo[i]; o--; ) {
int j = ej[i][o];

dfs3(j);
}
for (o = eo_[i]; o--; ) {
h = eh[i][o];
t_ = remove_(t_, 0, m * 2, idx[h << 1 | 0]);
t_ = remove_(t_, 0, m * 2, idx[h << 1 | 1]);
}
}

int main() {
int h, i, j;

scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 1; i < n; i++) {
scanf("%d", &pp[i]), pp[i]--;
append(ej, eo, pp[i], i);
}
dfs1(0, 0);
dfs2(0, 0);
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (h = 0; h < m; h++) {
scanf("%d%d", &i, &j), i--, j--;
ii[h << 1 | 0] = i, ii[h << 1 | 1] = j;
append(eh, eo_, lca(i, j), h);
}
for (h = 0; h < m * 2; h++)
hh_[h] = h;
sort(hh_, 0, m * 2);
for (h = 0; h < m * 2; h++)
idx[hh_[h]] = h;
for (h = 1; h < m * 2; h++)
dd1[h] = dd[lca(ii[hh_[h - 1]], ii[hh_[h]])];
build(0, m * 2);
ddmx[0] = -1;
d_ = 0, h1_ = 0, h2_ = 1, dfs3(0);
printf("%d\n", d_);
printf("%d %d\n", h1_ + 1, h2_ + 1);
return 0;
}```

### Compilation message

```sending.c: In function 'append':
sending.c:25:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
25 |  if (o >= 2 && (o & o - 1) == 0)
|                     ~~^~~
sending.c: In function 'main':
sending.c:250:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
250 |  scanf("%d%d", &n, &m);
|  ^~~~~~~~~~~~~~~~~~~~~
sending.c:254:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
254 |   scanf("%d", &pp[i]), pp[i]--;
|   ^~~~~~~~~~~~~~~~~~~
sending.c:262:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
262 |   scanf("%d%d", &i, &j), i--, j--;
|   ^~~~~~~~~~~~~~~~~~~~~```

#### Subtask #1 29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31164 KB Output is correct
9 Correct 3 ms 31068 KB Output is correct
10 Correct 3 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 3 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 4 ms 31208 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 3 ms 31064 KB Output is correct
18 Correct 3 ms 31064 KB Output is correct
19 Correct 4 ms 29016 KB Output is correct

#### Subtask #2 0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31164 KB Output is correct
9 Correct 3 ms 31068 KB Output is correct
10 Correct 3 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 3 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 4 ms 31208 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 3 ms 31064 KB Output is correct
18 Correct 3 ms 31064 KB Output is correct
19 Correct 4 ms 29016 KB Output is correct
20 Correct 14 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Incorrect 6 ms 31836 KB Output isn't correct
23 Halted 0 ms 0 KB -

#### Subtask #3 0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31164 KB Output is correct
9 Correct 3 ms 31068 KB Output is correct
10 Correct 3 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 3 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 4 ms 31208 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 3 ms 31064 KB Output is correct
18 Correct 3 ms 31064 KB Output is correct
19 Correct 4 ms 29016 KB Output is correct
20 Correct 14 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Incorrect 6 ms 31836 KB Output isn't correct
23 Halted 0 ms 0 KB -

#### Subtask #4 0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31164 KB Output is correct
9 Correct 3 ms 31068 KB Output is correct
10 Correct 3 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 3 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 4 ms 31208 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 3 ms 31064 KB Output is correct
18 Correct 3 ms 31064 KB Output is correct
19 Correct 4 ms 29016 KB Output is correct
20 Correct 14 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Incorrect 6 ms 31836 KB Output isn't correct
23 Halted 0 ms 0 KB -

#### Subtask #5 0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1246 ms 76056 KB Output is correct
2 Correct 3115 ms 75892 KB Output is correct
3 Correct 2021 ms 75852 KB Output is correct
4 Correct 4521 ms 76188 KB Output is correct
5 Correct 1195 ms 75604 KB Output is correct
6 Execution timed out 5031 ms 61296 KB Time limit exceeded
7 Halted 0 ms 0 KB -

#### Subtask #6 0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 75820 KB Output is correct
2 Correct 148 ms 75712 KB Output is correct
3 Correct 156 ms 84924 KB Output is correct
4 Correct 149 ms 80220 KB Output is correct
5 Correct 150 ms 80260 KB Output is correct
6 Execution timed out 5053 ms 76116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

#### Subtask #7 0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31164 KB Output is correct
9 Correct 3 ms 31068 KB Output is correct
10 Correct 3 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 3 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 4 ms 31208 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 3 ms 31064 KB Output is correct
18 Correct 3 ms 31064 KB Output is correct
19 Correct 4 ms 29016 KB Output is correct
20 Correct 14 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Incorrect 6 ms 31836 KB Output isn't correct
23 Halted 0 ms 0 KB -

#### Subtask #8 0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31164 KB Output is correct
9 Correct 3 ms 31068 KB Output is correct
10 Correct 3 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 3 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 4 ms 31208 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 3 ms 31064 KB Output is correct
18 Correct 3 ms 31064 KB Output is correct
19 Correct 4 ms 29016 KB Output is correct
20 Correct 14 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Incorrect 6 ms 31836 KB Output isn't correct
23 Halted 0 ms 0 KB -