#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 = 19;
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; */
int white[mxN] = {}, black[mxN] = {}, graph[mxN] = {};
ll cB, cW;
ll ans;
int TC = 5;
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); */
/* } */
/* } */
int 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] == TC) continue;
sz[x] += get_sz(y, x);
}
/* cout << "Size of " << x << " is " << sz[x] << nl; */
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] == TC || sz[y] * 2 < tot) continue;
return get_cen(y, x, tot);
}
return x;
}
void solve(int x, int p, ll dd) {
/* if(white.count(x)) { */
if(white[x] == TC) {
ans = min(ans, dd + cB);
cW = min(cW, dd);
}
/* else if(black.count(x)) { */
else if(black[x] == TC) {
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] == TC) continue;
solve(y, x, dd + w);
}
}
void decompose(int x, int p) {
int c = get_cen(x, p, get_sz(x, p));
/* cout << "Centroid is " << c << nl; */
/* cout << "size is " << sz[x] << nl; */
cW = cB = 1e18L;
/* if(white.count(c)) cW = 0; */
if(white[c] == TC) cW = 0;
/* else if(black.count(c)) cB = 0; */
else if(black[c] == TC) cB = 0;
/* if(white[c] == TC) cout << c << " is white\n"; */
/* if(black[c] == TC) cout << c << " is black\n"; */
solve(c, p, 0);
proc[c] = TC;
/* cout << nl; */
for(auto U : vt[c]) {
int d = U.fr;
if(proc[d] == TC) continue;
decompose(d, c);
}
}
long long Query(int S, int X[], int T, int Y[]) {
++TC;
/* cout << nl; */
/* cout << "TEST#" << TC << nl; */
vector<int> nodes;
/* graph.clear(); */
/* white.clear(); */
rep(i, 0, S - 1) {
int x = X[i];
/* white.insert(x); */
white[x] = TC;
/* if(!graph.count(x)) while(int(vt[x].size())) vt[x].pop_back(); */
/* graph.insert(x); */
if(graph[x] != TC) while(int(vt[x].size())) vt[x].pop_back();
graph[x] = TC;
/* proc[x] = 0; */
nodes.eb(x);
}
/* black.clear(); */
rep(i, 0, T - 1) {
int y = Y[i];
/* black.insert(y); */
black[y] = TC;
if(graph[y] != TC) while(int(vt[y].size())) vt[y].pop_back();
graph[y] = TC;
/* 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[a] != TC) while(int(vt[a].size())) vt[a].pop_back();
graph[a] = TC;
/* if(!graph.count(a)) while(int(vt[a].size())) vt[a].pop_back(); */
/* graph.insert(a); */
/* proc[a] = 0; */
vt[a].eb(b, distab);
/* cout << "Edge " << a << ' ' << b << ' ' << distab << nl; */
if(graph[b] != TC) while(int(vt[b].size())) vt[b].pop_back();
graph[b] = TC;
/* if(!graph.count(b)) while(int(vt[b].size())) vt[b].pop_back(); */
/* graph.insert(b); */
/* proc[b] = 0; */
vt[b].eb(a, distab);
/* cout << "Edge " << b << ' ' << a << ' ' << distab << nl; */
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[a] != TC) while(int(vt[a].size())) vt[a].pop_back();
graph[a] = TC;
/* if(!graph.count(a)) while(int(vt[a].size())) vt[a].pop_back(); */
/* graph.insert(a); */
/* proc[a] = 0; */
vt[a].eb(b, distab);
/* cout << "Edge " << a << ' ' << b << ' ' << distab << nl; */
if(graph[b] != TC) while(int(vt[b].size())) vt[b].pop_back();
graph[b] = TC;
/* if(!graph.count(b)) while(int(vt[b].size())) vt[b].pop_back(); */
/* graph.insert(b); */
vt[b].eb(a, distab);
/* cout << "Edge " << b << ' ' << a << ' ' << distab << nl; */
st.pop_back();
}
rep(i, 0, n - 1) {
/* if(white[i] == TC) cout << i << " is white\n"; */
/* if(black[i] == TC) cout << i << " is black\n"; */
/* if(graph[i] == TC) cout << i << " is graph:"; */
/* for(auto U : vt[i]) cout << U.fr << ' '; */
/* cout << nl; */
}
ans = 1e18L;
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:204:5: note: in expansion of macro 'rep'
204 | 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:216:5: note: in expansion of macro 'rep'
216 | 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:231:5: note: in expansion of macro 'rep'
231 | 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:241:5: note: in expansion of macro 'rep'
241 | rep(i, 1, int(nodes.size()) - 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:292:5: note: in expansion of macro 'rep'
292 | rep(i, 0, n - 1) {
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
39 ms |
58156 KB |
Output is correct |
| 2 |
Correct |
1100 ms |
67508 KB |
Output is correct |
| 3 |
Correct |
1439 ms |
72320 KB |
Output is correct |
| 4 |
Correct |
1328 ms |
72016 KB |
Output is correct |
| 5 |
Correct |
1057 ms |
72672 KB |
Output is correct |
| 6 |
Correct |
484 ms |
72020 KB |
Output is correct |
| 7 |
Correct |
1437 ms |
72072 KB |
Output is correct |
| 8 |
Correct |
1365 ms |
72152 KB |
Output is correct |
| 9 |
Correct |
1062 ms |
72552 KB |
Output is correct |
| 10 |
Correct |
482 ms |
72040 KB |
Output is correct |
| 11 |
Correct |
1450 ms |
72076 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
57948 KB |
Output is correct |
| 2 |
Correct |
1898 ms |
229540 KB |
Output is correct |
| 3 |
Correct |
2729 ms |
233952 KB |
Output is correct |
| 4 |
Correct |
1295 ms |
226940 KB |
Output is correct |
| 5 |
Correct |
2398 ms |
262064 KB |
Output is correct |
| 6 |
Correct |
2873 ms |
234700 KB |
Output is correct |
| 7 |
Correct |
2419 ms |
103048 KB |
Output is correct |
| 8 |
Correct |
1039 ms |
99860 KB |
Output is correct |
| 9 |
Correct |
1848 ms |
108592 KB |
Output is correct |
| 10 |
Correct |
2187 ms |
104960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
39 ms |
58156 KB |
Output is correct |
| 2 |
Correct |
1100 ms |
67508 KB |
Output is correct |
| 3 |
Correct |
1439 ms |
72320 KB |
Output is correct |
| 4 |
Correct |
1328 ms |
72016 KB |
Output is correct |
| 5 |
Correct |
1057 ms |
72672 KB |
Output is correct |
| 6 |
Correct |
484 ms |
72020 KB |
Output is correct |
| 7 |
Correct |
1437 ms |
72072 KB |
Output is correct |
| 8 |
Correct |
1365 ms |
72152 KB |
Output is correct |
| 9 |
Correct |
1062 ms |
72552 KB |
Output is correct |
| 10 |
Correct |
482 ms |
72040 KB |
Output is correct |
| 11 |
Correct |
1450 ms |
72076 KB |
Output is correct |
| 12 |
Correct |
12 ms |
57948 KB |
Output is correct |
| 13 |
Correct |
1898 ms |
229540 KB |
Output is correct |
| 14 |
Correct |
2729 ms |
233952 KB |
Output is correct |
| 15 |
Correct |
1295 ms |
226940 KB |
Output is correct |
| 16 |
Correct |
2398 ms |
262064 KB |
Output is correct |
| 17 |
Correct |
2873 ms |
234700 KB |
Output is correct |
| 18 |
Correct |
2419 ms |
103048 KB |
Output is correct |
| 19 |
Correct |
1039 ms |
99860 KB |
Output is correct |
| 20 |
Correct |
1848 ms |
108592 KB |
Output is correct |
| 21 |
Correct |
2187 ms |
104960 KB |
Output is correct |
| 22 |
Correct |
4674 ms |
252204 KB |
Output is correct |
| 23 |
Correct |
3893 ms |
251796 KB |
Output is correct |
| 24 |
Correct |
7461 ms |
256448 KB |
Output is correct |
| 25 |
Correct |
6604 ms |
258232 KB |
Output is correct |
| 26 |
Correct |
6001 ms |
251268 KB |
Output is correct |
| 27 |
Correct |
5305 ms |
276012 KB |
Output is correct |
| 28 |
Correct |
2203 ms |
246280 KB |
Output is correct |
| 29 |
Correct |
5777 ms |
250156 KB |
Output is correct |
| 30 |
Correct |
5760 ms |
247276 KB |
Output is correct |
| 31 |
Correct |
5328 ms |
250156 KB |
Output is correct |
| 32 |
Correct |
2476 ms |
116824 KB |
Output is correct |
| 33 |
Correct |
1149 ms |
111048 KB |
Output is correct |
| 34 |
Correct |
2083 ms |
107552 KB |
Output is correct |
| 35 |
Correct |
2149 ms |
109428 KB |
Output is correct |
| 36 |
Correct |
3054 ms |
110280 KB |
Output is correct |
| 37 |
Correct |
3003 ms |
108644 KB |
Output is correct |
