#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;
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 cB, cW;
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];
}
}
}
}
int lca(int x, int y) {
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;
x = par[x][j];
}
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];
}
x = par[x][0];
y = par[y][0];
assert(x == y);
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) {
if(white.count(x)) {
ans = min(ans, dd + cB);
cW = min(cW, dd);
}
else if(black.count(x)) {
ans = min(ans, dd + cW);
cB = min(cB, 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);
}
}
void decompose(int x, int p) {
int c = get_cen(x, p, get_sz(x, p));
cW = cB = 1e18L;
if(white.count(c)) cW = 0;
else if(black.count(c)) cB = 0;
solve(c, p, 0);
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[]) {
vector<int> nodes;
graph.clear();
white.clear();
rep(i, 0, S - 1) {
int x = X[i];
white.insert(x);
if(!graph.count(x)) while(int(vt[x].size())) vt[x].pop_back();
graph.insert(x);
proc[x] = 0;
nodes.eb(x);
}
black.clear();
rep(i, 0, T - 1) {
int y = Y[i];
black.insert(y);
if(!graph.count(y)) while(int(vt[y].size())) vt[y].pop_back();
graph.insert(y);
proc[y] = 0;
nodes.eb(y);
}
sort(nodes.begin(), nodes.end(), [&](int left, int right) {
return tin[left] < tin[right];
});
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());
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);
proc[a] = 0;
vt[a].eb(b, distab);
if(!graph.count(b)) while(int(vt[b].size())) vt[b].pop_back();
graph.insert(b);
proc[b] = 0;
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);
proc[a] = 0;
vt[a].eb(b, distab);
if(!graph.count(b)) while(int(vt[b].size())) vt[b].pop_back();
graph.insert(b);
proc[b] = 0;
vt[b].eb(a, distab);
st.pop_back();
}
ans = 1e18L;
/* for(int U : graph) { */
/* proc[U] = 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:190:5: note: in expansion of macro 'rep'
190 | 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:199:5: note: in expansion of macro 'rep'
199 | 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:211:5: note: in expansion of macro 'rep'
211 | 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:221:5: note: in expansion of macro 'rep'
221 | rep(i, 1, int(nodes.size()) - 1) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
53852 KB |
Output is correct |
| 2 |
Execution timed out |
8041 ms |
60944 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
53852 KB |
Output is correct |
| 2 |
Correct |
2508 ms |
218736 KB |
Output is correct |
| 3 |
Correct |
3674 ms |
223084 KB |
Output is correct |
| 4 |
Correct |
1536 ms |
216388 KB |
Output is correct |
| 5 |
Correct |
2596 ms |
250860 KB |
Output is correct |
| 6 |
Correct |
3596 ms |
223444 KB |
Output is correct |
| 7 |
Correct |
5175 ms |
93012 KB |
Output is correct |
| 8 |
Correct |
1579 ms |
91508 KB |
Output is correct |
| 9 |
Correct |
2634 ms |
97064 KB |
Output is correct |
| 10 |
Correct |
4367 ms |
93288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
53852 KB |
Output is correct |
| 2 |
Execution timed out |
8041 ms |
60944 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
