#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
#define repd(i, a, b) for(int (i) = (a); i >= (b); --i)
#define em emplace
#define eb emplace_back
#define pi pair<int, int>
#define fr first
#define sc second
#define mp make_pair
const char nl = '\n';
#warning using int and long long as well
using ll = long long;
/* #warning checkconstanst as per subtask */
const int mxN = 5e5L + 10;
const int logN = 20;
vector<pair<int, ll>> adj[mxN];
int n;
int par[mxN][logN + 1], dep[mxN];
ll dist[mxN][logN + 1];
int tmr = 0;
int tin[mxN], tout[mxN];
vector<pair<int, ll>> vt[mxN];
set<int> white, black, graph;
ll ans;
int TEST = 0;
void dfs(int x, int p) {
tin[x] = tmr++;
for(auto U : adj[x]) {
int y = U.first; ll w = U.second;
if(y == p) continue;
dep[y] = dep[x] + 1;
dist[y][0] = w;
par[y][0] = x;
dfs(y, x);
}
tout[x] = tmr++;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < N - 1; ++i) {
adj[A[i]].emplace_back(B[i], ll(D[i]));
adj[B[i]].emplace_back(A[i], ll(D[i]));
}
dep[0] = 0;
dist[0][0] = -1;
par[0][0] = -1;
dfs(0, -1);
for(int j = 1; j < logN; ++j) {
for(int i = 0; i < N; ++i) {
if(dep[i] < (1ll << j)) {
par[i][j] = dist[i][j] = -1;
}
else {
par[i][j] = par[par[i][j - 1]][j - 1];
dist[i][j] = dist[i][j - 1] + dist[par[i][j - 1]][j - 1];
}
}
}
/* rep(i, 0, n - 1) { */
/* cout << i << ": "; */
/* cout << dep[i] << ' ' << par[i][0] << ' ' << dist[i][0]; */
/* cout << nl; */
/* } */
}
int lca(int x, int y) {
/* cout << "Query of lca of " << x << ' ' << y << " = "; */
if(dep[x] < dep[y]) swap(x, y);
ll diff = dep[x] - dep[y];
/* cout << diff << ' '; */
for(int j = logN - 1; j >= 0; --j) {
if(!(diff & (1ll << j))) continue;
x = par[x][j];
}
/* cout << x << ' ' << y << ' '; */
/* if(x == y) cout << x << nl; */
if(x == y) return x;
for(int j = logN - 1; j >= 0; --j) {
if(par[x][j] == par[y][j]) continue;
x = par[x][j];
y = par[y][j];
}
/* cout << x << ' ' << y << ' '; */
x = par[x][0];
y = par[y][0];
assert(x == y);
/* cout << x << nl; */
return x;
}
ll distance(int x, int y) {
ll res = 0;
if(dep[x] < dep[y]) swap(x, y);
ll diff = dep[x] - dep[y];
for(int j = logN - 1; j >= 0; --j) {
if(!(diff & (1ll << j))) continue;
res += dist[x][j];
x = par[x][j];
}
if(x == y) return res;
for(int j = logN - 1; j >= 0; --j) {
if(par[x][j] == par[y][j]) continue;
res += dist[x][j];
x = par[x][j];
res += dist[y][j];
y = par[y][j];
}
res += dist[x][0];
x = par[x][0];
res += dist[y][0];
y = par[y][0];
assert(x == y);
return res;
}
bool contains(int up, int dn) {
return (tin[up] < tin[dn] && tout[dn] < tout[up]);
}
void solve(int x, int p, ll tot) {
if(black.count(x) && tot < ans) ans = tot;
for(auto U : vt[x]) {
int y = U.fr; ll w = U.sc;
if(y == p) continue;
solve(y, x, tot + w);
}
}
bool proc[mxN];
int sz[mxN];
int get_sz(int x, int p) {
sz[x] = 1;
for(auto U : vt[x]) {
int y = U.fr;
if(y == p || proc[y]) continue;
sz[x] += get_sz(y, x);
}
return sz[x];
}
int get_cen(int x, int p, int tot) {
for(auto U : vt[x]) {
int y = U.fr;
if(y == p || proc[y] || sz[p] * 2 <= tot) continue;
return get_cen(y, x, tot);
}
return x;
}
void solve(int x, int p, ll dd, int color) {
if(color == 1 && white.count(x)) ans = min(ans, dd);
if(color == 0 && black.count(x)) ans = min(ans, dd);
for(auto U : vt[x]) {
int y = U.fr; ll w = U.sc;
if(y == p || proc[y]) continue;
solve(y, x, dd + w, color);
}
}
void decompose(int x, int p) {
int c = get_cen(x, p, get_sz(x, p));
int color = -1;
if(white.count(c)) color = 0;
else if(black.count(c)) color = 1;
solve(c, p, 0, color);
proc[c] = 1;
for(auto U : vt[c]) {
int d = U.fr;
if(proc[d]) continue;
decompose(d, c);
}
}
long long Query(int S, int X[], int T, int Y[]) {
/* cout << nl; */
/* cout << "TESTCASE#" << ++TEST << nl; */
vector<int> nodes;
graph.clear();
white.clear();
rep(i, 0, S - 1) {
int x = X[i];
white.insert(x);
graph.insert(x);
while(int(vt[x].size())) vt[x].pop_back();
nodes.eb(x);
}
black.clear();
rep(i, 0, T - 1) {
int y = Y[i];
black.insert(y);
graph.insert(y);
while(int(vt[y].size())) vt[y].pop_back();
nodes.eb(y);
}
sort(nodes.begin(), nodes.end(), [&](int left, int right) {
return tin[left] < tin[right];
});
/* cout << "NODES: "; */
/* for(int i : nodes) cout << i << ' '; */
/* cout << nl; */
rep(i, 0, S + T - 2) {
nodes.eb(lca(nodes[i], nodes[i + 1]));
}
sort(nodes.begin(), nodes.end(), [&](int left, int right) {
return tin[left] < tin[right];
});
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
/* cout << "NODES: "; */
/* for(int i : nodes) cout << i << ' '; */
/* cout << nl; */
vector<int> st;
st.eb(nodes[0]);
rep(i, 1, int(nodes.size()) - 1) {
int u = nodes[i];
while(int(st.size()) >= 2 && !contains(st.back(), u)) {
int a = st[int(st.size()) - 1];
int b = st[int(st.size()) - 2];
ll distab = distance(a, b);
if(!graph.count(a)) while(int(vt[a].size())) vt[a].pop_back();
graph.insert(a);
vt[a].eb(b, distab);
/* cout << "Edge " << a << ' ' << b << ' ' << distab << nl; */
if(!graph.count(b)) while(int(vt[b].size())) vt[b].pop_back();
graph.insert(b);
vt[b].eb(a, distab);
st.pop_back();
}
st.eb(u);
}
while(int(st.size()) >= 2) {
int a = st[int(st.size()) - 1];
int b = st[int(st.size()) - 2];
ll distab = distance(a, b);
if(!graph.count(a)) while(int(vt[a].size())) vt[a].pop_back();
graph.insert(a);
vt[a].eb(b, distab);
/* cout << "Edge " << a << ' ' << b << ' ' << distab << nl; */
if(!graph.count(b)) while(int(vt[b].size())) vt[b].pop_back();
graph.insert(b);
vt[b].eb(a, distab);
st.pop_back();
}
ans = 1e18;
for(int U : graph) {
proc[U] = 0;
}
for(int w : white) {
solve(w, -1, 0);
}
/* decompose(X[0], -1); */
return ans;
}
Compilation message
factories.cpp:18:2: warning: #warning using int and long long as well [-Wcpp]
18 | #warning using int and long long as well
| ^~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:5:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:198:5: note: in expansion of macro 'rep'
198 | rep(i, 0, S - 1) {
| ^~~
factories.cpp:5:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:206:5: note: in expansion of macro 'rep'
206 | rep(i, 0, T - 1) {
| ^~~
factories.cpp:5:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:220:5: note: in expansion of macro 'rep'
220 | rep(i, 0, S + T - 2) {
| ^~~
factories.cpp:5:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:233:5: note: in expansion of macro 'rep'
233 | rep(i, 1, int(nodes.size()) - 1) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
53848 KB |
Output is correct |
| 2 |
Execution timed out |
8101 ms |
61028 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
53848 KB |
Output is correct |
| 2 |
Correct |
2089 ms |
218672 KB |
Output is correct |
| 3 |
Correct |
3011 ms |
222708 KB |
Output is correct |
| 4 |
Correct |
1466 ms |
215856 KB |
Output is correct |
| 5 |
Correct |
2619 ms |
250868 KB |
Output is correct |
| 6 |
Correct |
3211 ms |
223384 KB |
Output is correct |
| 7 |
Correct |
3537 ms |
93068 KB |
Output is correct |
| 8 |
Correct |
1674 ms |
91364 KB |
Output is correct |
| 9 |
Correct |
2442 ms |
96648 KB |
Output is correct |
| 10 |
Correct |
3055 ms |
93240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
53848 KB |
Output is correct |
| 2 |
Execution timed out |
8101 ms |
61028 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
