#include <bits/stdc++.h>
#include "factories.h"
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define eb emplace_back
#define F first
#define S second
const ll ool = 1e18 + 9;
const int NN = 1e6 + 6, C = 20, oo = 1e9 + 9;
int n, tin[NN], timer, lg[NN];
bool tp1[NN], tp2[NN];
ll lvl[NN], d[NN][2];
pair < ll, int > mn[C + 1][NN];
vector < pair < int, ll > > g[NN];
void dfs(int v, int par) {
tin[v] = ++timer;
mn[0][timer] = mkp(lvl[v], v);
if (timer > 1) lg[timer] = lg[timer >> 1] + 1;
for (auto it : g[v]) {
int to = it.F;
if (to == par) continue;
lvl[to] = lvl[v] + it.S;
dfs(to, v);
mn[0][++timer] = mkp(lvl[v], v);
if (timer > 1) lg[timer] = lg[timer >> 1] + 1;
}
}
ll dfs2(int v, int par) {
d[v][0] = d[v][1] = ool;
ll res = ool;
if (tp1[v]) d[v][0] = 0;
if (tp2[v]) d[v][1] = 0;
for (auto it : g[v]) {
int to = it.F;
if (to == par) continue;
res = min(res, dfs2(to, v));
d[v][0] = min(d[v][0], d[to][0] + it.S);
d[v][1] = min(d[v][1], d[to][1] + it.S);
}
//cerr << v << " " << d[v][0] << " " << d[v][1] << "\n";
return min(res, d[v][0] + d[v][1]);
}
int get(int l, int r) {
if (l > r) swap(l, r);
int deg = lg[r - l + 1];
return min(mn[deg][l], mn[deg][r - (1 << deg) + 1]).S;
}
void Init(int _n, int A[], int B[], int D[]) {
n = _n;
forn(i, 0, n - 2) {
g[A[i] + 1].eb(B[i] + 1, D[i]);
g[B[i] + 1].eb(A[i] + 1, D[i]);
}
dfs(1, 0);
forn(i, 1, C) {
forn(j, 1, timer - (1 << i) + 1) {
mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
}
}
}
ll Query(int S, int X[], int T, int Y[]) {
if (S <= 20 && T <= 20) {
ll res = ool;
forn(i, 0, S - 1) {
forn(j, 0, T - 1) {
int v = X[i] + 1, u = Y[j] + 1;
int lca = get(tin[u], tin[v]);
res = min(res, lvl[u] + lvl[v] - 2 * lvl[lca]);
if (!res) break;
}
if (!res) break;
}
return res;
}
// forn(i, 0, S - 1) cerr << X[i] << " ";
// cerr << "\n";
// forn(i, 0, T - 1) cerr << Y[i] << " ";
// cerr << "\n";
forn(i, 0, S - 1)
tp1[X[i] + 1] = 1;
forn(i, 0, T - 1)
tp2[Y[i] + 1] = 1;
ll res = dfs2(1, 0);
forn(i, 0, S - 1)
tp1[X[i] + 1] = 0;
forn(i, 0, T - 1)
tp2[Y[i] + 1] = 0;
return res;
}
#ifdef krauch
#define MAX_N 500000
#define MAX_Q 100000
#define MAX_SUM_ST 1000000
#define MAX_VALUE 1000000000
int N, Q;
int A[MAX_N], B[MAX_N], D[MAX_N];
int S[MAX_N];
int T[MAX_N];
int X[MAX_SUM_ST];
int Y[MAX_SUM_ST];
int Qx[MAX_N];
int Qy[MAX_N];
int main() {
freopen("sample-in-01.txt","r",stdin);
int i, j, k;
int STop, TTop;
if (2 != scanf("%d%d", &N, &Q)) {
fprintf(stderr, "error: cannot read N and Q.\n");
exit(1);
}
if (!(2 <= N && N <= MAX_N)) {
fprintf(stderr, "error: N is out of bounds.\n");
exit(1);
}
if (!(1 <= Q && Q <= MAX_Q)) {
fprintf(stderr, "error: Q is out of bounds.\n");
exit(1);
}
for (i = 0; i < N - 1; ++i) {
if (1 != scanf("%d", &A[i])) {
fprintf(stderr, "error: cannot read A[%d].\n", i);
exit(1);
}
if (!(0 <= A[i] && A[i] <= N - 1)) {
fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
exit(1);
}
if (1 != scanf("%d", &B[i])) {
fprintf(stderr, "error: cannot read B[%d].\n", i);
exit(1);
}
if (!(0 <= B[i] && B[i] <= N - 1)) {
fprintf(stderr, "error: B[%d] is out of bounds.\n", i);
exit(1);
}
if (A[i] == B[i]) {
fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i);
exit(1);
}
if (1 != scanf("%d", &D[i])) {
fprintf(stderr, "error: cannot read D[%d].\n", i);
exit(1);
}
if (!(1 <= D[i] && D[i] <= MAX_VALUE)) {
fprintf(stderr, "error: D[%d] is out of bounds.\n", i);
exit(1);
}
}
STop = 0;
TTop = 0;
for (j = 0; j < Q; ++j) {
if (2 != scanf("%d%d", &S[j], &T[j])) {
fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
exit(1);
}
if(STop + S[j] > MAX_SUM_ST) {
fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j);
exit(1);
}
if(TTop + T[j] > MAX_SUM_ST) {
fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j);
exit(1);
}
for (k = 0; k < S[j]; ++k, ++STop) {
if (1 != scanf("%d", &X[STop])) {
fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
exit(1);
}
if (!(0 <= X[STop] && X[STop] <= N - 1)) {
fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
exit(1);
}
}
for (k = 0; k < T[j]; ++k, ++TTop) {
if (1 != scanf("%d", &Y[TTop])) {
fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
exit(1);
}
if (!(0 <= Y[TTop] && Y[TTop] <= N - 1)) {
fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
exit(1);
}
}
}
STop = 0;
TTop = 0;
Init(N, A, B, D);
for (j = 0; j < Q; ++j) {
for (k = 0; k < S[j]; k++) {
Qx[k] = X[STop++];
}
for (k = 0; k < T[j]; k++) {
Qy[k] = Y[TTop++];
}
printf("%lld\n", Query(S[j], Qx, T[j], Qy));
}
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
409056 KB |
Output is correct |
| 2 |
Correct |
604 ms |
409320 KB |
Output is correct |
| 3 |
Correct |
1717 ms |
409320 KB |
Output is correct |
| 4 |
Correct |
1330 ms |
409320 KB |
Output is correct |
| 5 |
Correct |
626 ms |
409544 KB |
Output is correct |
| 6 |
Correct |
387 ms |
409344 KB |
Output is correct |
| 7 |
Correct |
1630 ms |
409320 KB |
Output is correct |
| 8 |
Correct |
1312 ms |
409320 KB |
Output is correct |
| 9 |
Correct |
707 ms |
409544 KB |
Output is correct |
| 10 |
Correct |
416 ms |
409344 KB |
Output is correct |
| 11 |
Correct |
1632 ms |
409320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
409056 KB |
Output is correct |
| 2 |
Correct |
1378 ms |
434664 KB |
Output is correct |
| 3 |
Correct |
1454 ms |
438188 KB |
Output is correct |
| 4 |
Correct |
1092 ms |
432852 KB |
Output is correct |
| 5 |
Correct |
1319 ms |
455072 KB |
Output is correct |
| 6 |
Correct |
1384 ms |
437872 KB |
Output is correct |
| 7 |
Correct |
1545 ms |
414716 KB |
Output is correct |
| 8 |
Correct |
1082 ms |
414300 KB |
Output is correct |
| 9 |
Correct |
964 ms |
416648 KB |
Output is correct |
| 10 |
Correct |
1087 ms |
414636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6000 ms |
434664 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
