/*input
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "factories.h"
using namespace std;
namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
}
using namespace my_template;
const int MOD = 1000000007;
const ll INF = 1e14;
const int MX = 500101;
const int L = 19;
int n;
vector<vector<pair<int, ll>>> edges;
vi dep;
vl toRoot;
vii p;
vll w;
vi in;
vi out;
int piv;
void dfs(int x, int par) {
in[x] = piv++;
for (auto u : edges[x]) {
if (u.x == par) continue;
int b = u.x;
dep[b] = dep[x] + 1;
toRoot[b] = toRoot[x] + u.y;
p[b][0] = x;
w[b][0] = u.y;
for (int i = 1; i < L; ++i)
{
p[b][i] = p[p[b][i - 1]][i - 1];
w[b][i] = w[b][i - 1] + w[p[b][i - 1]][i - 1];
}
dfs(u.x, x);
}
out[x] = piv;
}
// a is ancestor of b
int anc(int a, int b) {
return in[a] < in[b] and out[b] <= out[a];
}
int lca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
// a
// b
for (int i = L - 1; i >= 0; --i)
{
if (dep[b] - (1 << i) >= dep[a])
b = p[b][i];
}
assert(dep[a] == dep[b]);
if (a == b) return a;
for (int i = L - 1; i >= 0; i--)
{
if (p[a][i] != p[b][i]) {
a = p[a][i];
b = p[b][i];
}
}
return p[a][0];
}
ll dis(int a, int b) {
int l = lca(a, b);
return toRoot[a] + toRoot[b] - 2 * toRoot[l];
}
void make_lca() {
dep = vi(n);
p = vii(n, vi(L, 0));
w = vll(n, vl(L, 0));
toRoot = vl(n);
in = vi(n);
out = vi(n);
dep[0] = 0;
p[0][0] = 0;
w[0][0] = 0;
toRoot[0] = 0;
piv = 0;
dfs(0, -1);
}
vi kas;
void Init(int N, int A[], int B[], int D[]) {
n = N;
edges.resize(N);
kas = vi(N, -1);
for (int i = 0; i < N - 1; ++i)
{
int a = A[i];
int b = B[i];
int d = D[i];
edges[a].emplace_back(b, d);
edges[b].emplace_back(a, d);
}
make_lca();
}
ll Query(int S, int X[], int T, int Y[]) {
vi visi;
for (int i = 0; i < S; ++i) {
visi.emplace_back(X[i]);
kas[X[i]] = 1;
}
for (int i = 0; i < T; ++i) {
visi.emplace_back(Y[i]);
kas[Y[i]] = 2;
}
sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
return in[a] < in[b];
});
for (int i = 1; i < S + T; ++i)
{
int l = lca(visi[i - 1], visi[i]);
visi.emplace_back(l);
if (kas[l] == -1)
kas[l] = 0;
}
sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
return in[a] < in[b];
});
visi.erase(unique(visi.begin(), visi.end()), visi.end());
// print(visi);
ll ats = INF;
unordered_map<int, vl> low;
vector<int> ver;
ver.emplace_back(visi[0]);
low[visi[0]] = vl{INF, INF};
if (kas[visi[0]]) low[visi[0]][kas[visi[0]] - 1] = 0;
for (int i = 1; i < (int)visi.size(); ++i)
{
while (!anc(ver.back(), visi[i])) {
int a = ver.back(); ver.pop_back();
int b = ver.back();
ll d = dis(a, b);
if (kas[a] + kas[b] == 3)
ats = min(ats, d);
// b
// / c
// a
low[b][0] = min(low[b][0], low[a][0] + d);
low[b][1] = min(low[b][1], low[a][1] + d);
}
ver.emplace_back(visi[i]);
low[visi[i]] = vl{INF, INF};
if (kas[visi[i]]) low[visi[i]][kas[visi[i]] - 1] = 0;
}
while (ver.size() >= 2) {
int a = ver.back(); ver.pop_back();
int b = ver.back();
ll d = dis(a, b);
// printf("a = %d, b = %d, d = %lld\n", a, b, d);
if (kas[a] + kas[b] == 3)
ats = min(ats, d);
// b
// / c
// a
low[b][0] = min(low[b][0], low[a][0] + d);
low[b][1] = min(low[b][1], low[a][1] + d);
}
for (auto u : visi) {
// printf("u = %d, low = %lld %lld\n", u, low[u][0], low[u][1]);
ats = min(ats, low[u][0] + low[u][1]);
kas[u] = -1;
}
return ats;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
1004 KB |
Output is correct |
2 |
Correct |
1845 ms |
10936 KB |
Output is correct |
3 |
Correct |
2076 ms |
10924 KB |
Output is correct |
4 |
Correct |
1932 ms |
11212 KB |
Output is correct |
5 |
Correct |
1665 ms |
11340 KB |
Output is correct |
6 |
Correct |
1346 ms |
11100 KB |
Output is correct |
7 |
Correct |
2070 ms |
10988 KB |
Output is correct |
8 |
Correct |
1956 ms |
11268 KB |
Output is correct |
9 |
Correct |
1660 ms |
11380 KB |
Output is correct |
10 |
Correct |
1339 ms |
11060 KB |
Output is correct |
11 |
Correct |
2065 ms |
10732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
620 KB |
Output is correct |
2 |
Correct |
3146 ms |
211096 KB |
Output is correct |
3 |
Correct |
5580 ms |
215020 KB |
Output is correct |
4 |
Correct |
2102 ms |
208732 KB |
Output is correct |
5 |
Correct |
5148 ms |
245424 KB |
Output is correct |
6 |
Correct |
6052 ms |
216248 KB |
Output is correct |
7 |
Correct |
5573 ms |
51404 KB |
Output is correct |
8 |
Correct |
2123 ms |
64904 KB |
Output is correct |
9 |
Correct |
4630 ms |
69868 KB |
Output is correct |
10 |
Correct |
5625 ms |
66540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
1004 KB |
Output is correct |
2 |
Correct |
1845 ms |
10936 KB |
Output is correct |
3 |
Correct |
2076 ms |
10924 KB |
Output is correct |
4 |
Correct |
1932 ms |
11212 KB |
Output is correct |
5 |
Correct |
1665 ms |
11340 KB |
Output is correct |
6 |
Correct |
1346 ms |
11100 KB |
Output is correct |
7 |
Correct |
2070 ms |
10988 KB |
Output is correct |
8 |
Correct |
1956 ms |
11268 KB |
Output is correct |
9 |
Correct |
1660 ms |
11380 KB |
Output is correct |
10 |
Correct |
1339 ms |
11060 KB |
Output is correct |
11 |
Correct |
2065 ms |
10732 KB |
Output is correct |
12 |
Correct |
6 ms |
620 KB |
Output is correct |
13 |
Correct |
3146 ms |
211096 KB |
Output is correct |
14 |
Correct |
5580 ms |
215020 KB |
Output is correct |
15 |
Correct |
2102 ms |
208732 KB |
Output is correct |
16 |
Correct |
5148 ms |
245424 KB |
Output is correct |
17 |
Correct |
6052 ms |
216248 KB |
Output is correct |
18 |
Correct |
5573 ms |
51404 KB |
Output is correct |
19 |
Correct |
2123 ms |
64904 KB |
Output is correct |
20 |
Correct |
4630 ms |
69868 KB |
Output is correct |
21 |
Correct |
5625 ms |
66540 KB |
Output is correct |
22 |
Correct |
7007 ms |
247492 KB |
Output is correct |
23 |
Correct |
5935 ms |
249432 KB |
Output is correct |
24 |
Execution timed out |
8080 ms |
251600 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |