#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define forinc(a, b, c) for(int a = b, _c = c; a <= _c; ++a)
#define fordec(a, b, c) for(int a = b, _c = c; a >= _c; --a)
#define rep(i, a) forinc(i, 1, a)
#define repv(i, a) forinc(i, 0, a - 1)
#define forv(a, b) for(auto &a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define reset(f, x) memset(f, x, sizeof(f))
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define bit(x, i) (x >> (i - 1) & 1ll)
#define on(x, i) (x | (1ll << (i - 1)))
#define off(x, i) (x & ~(1ll << (i - 1)))
const int N = 5e5 + 5;
const int _N = 5005;
const long long INF = 1e16;
int n, que;
vector<ii> ad[N];
int st[N], en[N], id, pd[N][25], dd[N];
long long d[N], ans, pf[N], sf[N];
void Init(int n, int A[], int B[], int D[]) {
repv(i, n - 1) {
int u = A[i], v = B[i], c = D[i];
u++; v++;
ad[u].eb(v, c);
ad[v].eb(u, c);
}
function<void(int, int)> dfs = [&](int u, int par) {
st[u] = ++id;
forinc(i, 1, 20) pd[u][i] = pd[pd[u][i - 1]][i - 1];
forv(v, ad[u]) if(v.fi != par) {
pd[v.fi][0] = u;
d[v.fi] = d[u] + v.se;
dfs(v.fi, u);
}
en[u] = ++id;
};
dfs(1, 0);
forinc(i, 1, n) ad[i].clear();
}
int anc(int u, int v) {
return (st[u] <= st[v] && en[u] >= en[v]) || !u;
}
int lca(int u, int v){
if(anc(u, v)) return u;
if(anc(v, u)) return v;
fordec(i, 20, 0) if(!anc(pd[u][i], v)) u = pd[u][i];
return pd[u][0];
}
bool cmp(int x, int y) {return make_pair(st[x], en[x]) < make_pair(st[y], en[y]);}
int dist(int u, int v) {return d[u] + d[v] - 2 * d[lca(u, v)];}
long long Query(int s, int S[], int t, int T[]) {
vector<int> no;
repv(i, s) no.pb(S[i] + 1), dd[S[i] + 1] = 1;
repv(i, t) no.pb(T[i] + 1), dd[T[i] + 1] |= 2;
sort(all(no), cmp);
repv(i, no.size() - 1) no.pb(lca(no[i], no[i + 1]));
sort(all(no)); no.erase(unique(all(no)), end(no));
sort(all(no), cmp);
stack<int> kek;
forv(v, no) {
while(kek.size() && en[v] >= en[kek.top()]) kek.pop();
if(kek.size()) {
ad[kek.top()].eb(v, dist(kek.top(), v));
}
kek.push(v);
}
ans = INF;
function<void(int)> dfs = [&](int u) {
long long &x = pf[u], &y = sf[u];
x = (dd[u] & 1) ? 0 : INF;
y = (dd[u] & 2) ? 0 : INF;
forv(v, ad[u]) {
dfs(v.fi);
x = min(x, pf[v.fi] + v.se);
y = min(y, sf[v.fi] + v.se);
}
ans = min(ans, x + y);
};
dfs(no[0]);
forv(v, no) pf[v] = sf[v] = dd[v] = 0, ad[v].clear();
return ans;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//if(fopen("inp.txt", "r")){
//freopen("inp.txt", "r", stdin);
//}
cin >> n >> que;
static int A[_N], B[_N], D[_N];
repv(i, n - 1) cin >> A[i] >> B[i] >> D[i];
Init(n, A, B, D);
while(que--) {
int s, t;
cin >> s >> t;
static int S[N], T[N];
repv(i, s) cin >> S[i];
repv(i, t) cin >> T[i];
cout << Query(s, S, t, T) << '\n';
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
12672 KB |
Output is correct |
| 2 |
Correct |
1323 ms |
27640 KB |
Output is correct |
| 3 |
Correct |
1328 ms |
27828 KB |
Output is correct |
| 4 |
Incorrect |
1298 ms |
27768 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12416 KB |
Output is correct |
| 2 |
Correct |
1922 ms |
110328 KB |
Output is correct |
| 3 |
Incorrect |
2558 ms |
112888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
12672 KB |
Output is correct |
| 2 |
Correct |
1323 ms |
27640 KB |
Output is correct |
| 3 |
Correct |
1328 ms |
27828 KB |
Output is correct |
| 4 |
Incorrect |
1298 ms |
27768 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
