#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
vector<vector<int>> S, E;
vector<int> P, L, I, O;
vector<ll> D;
vector<bool> U, V;
int lca(int x, int y) {
if(L[x] < L[y]) swap(x, y);
int c = L[x] - L[y];
for(int i = 19; i >= 0; i--)
if((c>>i)&1)
x = S[x][i];
if(x == y) return x;
for(int i = 19; i >= 0; i--)
if(S[x][i] != S[y][i])
x = S[x][i], y = S[y][i];
return S[x][0];
}
void make_sparse() {
S.resize(P.size(), vector<int>(20));
for(int i = 0; i < P.size(); i++) S[i][0] = P[i];
for(int i = 0; i < P.size(); i++)
for(int j = 1; j < 20; j++)
S[i][j] = S[S[i][j-1]][j-1];
}
void dfs(int x, int p, int &cnt, vector<vector<pii>> &E) {
I[x] = cnt++;
for(auto &i : E[x]) {
if(i.fi == p) continue;
L[cnt] = L[I[x]]+1;
D[cnt] = D[I[x]]+i.se;
P[cnt] = I[x];
dfs(i.fi, x, cnt, E);
}
O[x] = cnt;
}
plll solve(int x) {
plll ans = {LLINF, {LLINF, LLINF}};
if(U[x]) ans.se.fi = 0LL;
if(V[x]) ans.se.se = 0LL;
U[x] = V[x] = false;
for(auto i : E[x]) {
plll tmp = solve(i);
ans.fi = min(ans.fi, tmp.fi);
ans.se.fi = min(ans.se.fi, tmp.se.fi + D[i] - D[x]);
ans.se.se = min(ans.se.se, tmp.se.se + D[i] - D[x]);
}
ans.fi = min(ans.fi, ans.se.fi+ans.se.se);
return ans;
}
void sort_vertex(vector<int> &vertex) {
sort(vertex.begin(), vertex.end());
vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());
}
void make_tree(vector<int> &M) {
int tmpsize = M.size();
for(int i = 1; i < tmpsize; i++) M.push_back(lca(M[i-1], M[i]));
sort_vertex(M);
for(int i = 1; i < M.size(); i++) E[lca(M[i-1], M[i])].push_back(M[i]);
}
void Init(int N, int A[], int B[], int X[]) {
vector<vector<pii>> T(N);
for(int i = 0; i < N-1; i++) {
T[A[i]].push_back({B[i], X[i]});
T[B[i]].push_back({A[i], X[i]});
}
I.resize(N); O.resize(N); P.resize(N);
D.resize(N, 0LL); L.resize(N, 0);
int cnt = 0;
dfs(0, 0, cnt, T);
make_sparse();
U.resize(N, false); V.resize(N, false); E.resize(N);
}
ll Query(int S, int X[], int T, int Y[]) {
//cout << "query " << S << " " << T << "\n";
vector<int> XX(X, X+S), YY(Y, Y+T), M;
for(auto i : XX) { M.push_back(I[i]); U[I[i]] = true; }
for(auto i : YY) { M.push_back(I[i]); V[I[i]] = true; }
sort_vertex(M);
make_tree(M);
plll ans = solve(M[0]);
assert(ans.se.fi < LLINF && ans.se.se < LLINF);
for(auto i : M) E[i].clear();
return ans.fi;
}
Compilation message
factories.cpp: In function 'void make_sparse()':
factories.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0; i < P.size(); i++) S[i][0] = P[i];
| ~~^~~~~~~~~~
factories.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0; i < P.size(); i++)
| ~~^~~~~~~~~~
factories.cpp: In function 'void make_tree(std::vector<int>&)':
factories.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 1; i < M.size(); i++) E[lca(M[i-1], M[i])].push_back(M[i]);
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
596 KB |
Output is correct |
2 |
Correct |
803 ms |
18940 KB |
Output is correct |
3 |
Correct |
871 ms |
19100 KB |
Output is correct |
4 |
Correct |
852 ms |
18964 KB |
Output is correct |
5 |
Correct |
654 ms |
19236 KB |
Output is correct |
6 |
Correct |
551 ms |
18892 KB |
Output is correct |
7 |
Correct |
884 ms |
18932 KB |
Output is correct |
8 |
Correct |
816 ms |
19064 KB |
Output is correct |
9 |
Correct |
648 ms |
19164 KB |
Output is correct |
10 |
Correct |
550 ms |
18944 KB |
Output is correct |
11 |
Correct |
869 ms |
18980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
Output is correct |
2 |
Correct |
1716 ms |
128144 KB |
Output is correct |
3 |
Correct |
2846 ms |
134352 KB |
Output is correct |
4 |
Correct |
1195 ms |
130524 KB |
Output is correct |
5 |
Correct |
2382 ms |
159020 KB |
Output is correct |
6 |
Correct |
2794 ms |
131112 KB |
Output is correct |
7 |
Correct |
2187 ms |
42112 KB |
Output is correct |
8 |
Correct |
1076 ms |
41592 KB |
Output is correct |
9 |
Correct |
2043 ms |
44852 KB |
Output is correct |
10 |
Correct |
2186 ms |
41972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
596 KB |
Output is correct |
2 |
Correct |
803 ms |
18940 KB |
Output is correct |
3 |
Correct |
871 ms |
19100 KB |
Output is correct |
4 |
Correct |
852 ms |
18964 KB |
Output is correct |
5 |
Correct |
654 ms |
19236 KB |
Output is correct |
6 |
Correct |
551 ms |
18892 KB |
Output is correct |
7 |
Correct |
884 ms |
18932 KB |
Output is correct |
8 |
Correct |
816 ms |
19064 KB |
Output is correct |
9 |
Correct |
648 ms |
19164 KB |
Output is correct |
10 |
Correct |
550 ms |
18944 KB |
Output is correct |
11 |
Correct |
869 ms |
18980 KB |
Output is correct |
12 |
Correct |
3 ms |
468 KB |
Output is correct |
13 |
Correct |
1716 ms |
128144 KB |
Output is correct |
14 |
Correct |
2846 ms |
134352 KB |
Output is correct |
15 |
Correct |
1195 ms |
130524 KB |
Output is correct |
16 |
Correct |
2382 ms |
159020 KB |
Output is correct |
17 |
Correct |
2794 ms |
131112 KB |
Output is correct |
18 |
Correct |
2187 ms |
42112 KB |
Output is correct |
19 |
Correct |
1076 ms |
41592 KB |
Output is correct |
20 |
Correct |
2043 ms |
44852 KB |
Output is correct |
21 |
Correct |
2186 ms |
41972 KB |
Output is correct |
22 |
Correct |
2423 ms |
129860 KB |
Output is correct |
23 |
Correct |
2602 ms |
130816 KB |
Output is correct |
24 |
Correct |
2478 ms |
132756 KB |
Output is correct |
25 |
Correct |
2956 ms |
134160 KB |
Output is correct |
26 |
Correct |
4566 ms |
133200 KB |
Output is correct |
27 |
Correct |
2826 ms |
153960 KB |
Output is correct |
28 |
Correct |
1612 ms |
131516 KB |
Output is correct |
29 |
Correct |
4520 ms |
132704 KB |
Output is correct |
30 |
Correct |
4576 ms |
132160 KB |
Output is correct |
31 |
Correct |
4559 ms |
132912 KB |
Output is correct |
32 |
Correct |
1260 ms |
49244 KB |
Output is correct |
33 |
Correct |
855 ms |
41656 KB |
Output is correct |
34 |
Correct |
1720 ms |
40976 KB |
Output is correct |
35 |
Correct |
1747 ms |
40996 KB |
Output is correct |
36 |
Correct |
1992 ms |
41608 KB |
Output is correct |
37 |
Correct |
2171 ms |
41608 KB |
Output is correct |