#include "factories.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int N = 500001, L = 19;
vector<pair<ll, ll>> g[N];
vector<int> cg[N];
int tin[N], tout[N], ct, h[N], up[L][N];
ll d1[N], d2[N], inf = 1e16;
void dfs(int v, int p) {
up[0][v] = p;
tin[v] = ++ct;
for (auto &u : g[v])
if (u.first != p) {
h[u.first] = h[v] + u.second;
dfs(u.first, v);
}
tout[v] = ++ct;
}
int lca(int u, int v) {
if (h[u] > h[v])
swap(u, v);
for (int i = L - 1; i >= 0; i--)
if (h[up[i][v]] >= h[u])
v = up[i][v];
if (u == v)
return u;
for (int i = L - 1; i >= 0; i--)
if (up[i][u] != up[i][v]) {
u = up[i][u];
v = up[i][v];
}
return up[0][u];
}
ll dfs2(int v) {
ll ans = inf;
for (int u : cg[v]) {
ans = min(ans, dfs2(u));
int cd = h[u] - h[v];
ans = min(ans, min(d1[v] + d2[u], d1[u] + d2[v]) + cd);
d1[v] = min(d1[v], d1[u] + cd);
d2[v] = min(d2[v], d2[u] + cd);
}
return ans;
}
void Init(int n, int a[], int b[], int d[]) {
rep(i, n - 1) {
g[a[i]].push_back({b[i], d[i]});
g[b[i]].push_back({a[i], d[i]});
}
dfs(0, 0);
rep(i, L - 1)
rep(j, n)
up[i + 1][j] = up[i][up[i][j]];
rep(i, n)
d1[i] = d2[i] = inf;
}
long long Query(int s, int x[], int t, int y[]) {
vector<int> li;
rep(i, s) {
li.push_back(x[i]);
d1[x[i]] = 0;
}
rep(i, t) {
li.push_back(y[i]);
d2[y[i]] = 0;
}
sort(all(li), [](int v1, int v2) {return tin[v1] < tin[v2];});
int k = li.size();
rep(i, k - 1)
li.push_back(lca(li[i], li[i + 1]));
sort(all(li), [](int v1, int v2) {return tin[v1] < tin[v2];});
vector<int> st;
for (int i : li) {
if (st.empty())
st.push_back(i);
else {
while (tout[st.back()] < tout[i])
st.pop_back();
if (st.back() == i)
continue;
assert(!st.empty());
cg[st.back()].push_back(i);
st.push_back(i);
}
}
ll ans = dfs2(li[0]);
for (int i : li) {
cg[i].clear();
d1[i] = d2[i] = inf;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
24568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
24192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
24568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
