| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 387528 | aryan12 | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
const long long MAXN = 5e5 + 5;
vector<pair<long long, long long> > g[MAXN];
long long Subtree[MAXN], lastCnt[MAXN], centroidParent[MAXN];
long long distFromRoot[MAXN], ans[MAXN];
bool isTaken[MAXN];
long long DP[20][MAXN], depth[MAXN];
long long cnt = 0;
void FindDist(long long node, long long par) {
DP[0][node] = par;
for(long long i = 0; i < g[node].size(); i++) {
if(g[node][i].first != par) {
distFromRoot[g[node][i].first] = distFromRoot[node] + g[node][i].second;
depth[g[node][i].first] = depth[node] + 1;
FindDist(g[node][i].first, node);
}
}
}
long long SubtreeDfs(long long node, long long par) {
Subtree[node] = 1;
for(long long i = 0; i < g[node].size(); i++) {
if(!isTaken[g[node][i].first] && !isTaken[node] && g[node][i].first != par) {
Subtree[node] += SubtreeDfs(g[node][i].first, node);
}
}
return Subtree[node];
}
long long FindCentroid(long long node, long long par, long long totalSize) {
for(long long i = 0; i < g[node].size(); i++) {
if(!isTaken[g[node][i].first] && !isTaken[node] && g[node][i].first != par) {
if(Subtree[g[node][i].first] > totalSize / 2) {
return FindCentroid(g[node][i].first, node, totalSize);
}
}
}
return node;
}
void BuildCentroid(long long centroid, long long par) {
long long siz = SubtreeDfs(centroid, -1);
centroid = FindCentroid(centroid, par, siz);
isTaken[centroid] = true;
if(par == -1)
centroidParent[centroid] = centroid;
else
centroidParent[centroid] = par;
for(long long i = 0; i < g[centroid].size(); i++) {
if(!isTaken[g[centroid][i].first]) {
BuildCentroid(g[centroid][i].first, centroid);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
for(long long i = 0; i < MAXN; i++) {
isTaken[i] = false;
Subtree[i] = 0;
distFromRoot[i] = 0;
centroidParent[i] = i;
lastCnt[i] = 0;
ans[i] = 1e15;
}
cnt = 0;
for(long long i = 0; i < N - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
distFromRoot[0] = 0;
depth[0] = 0;
FindDist(0, -1);
BuildCentroid(0, -1);
for(long long i = 1; i < 20; i++) {
for(long long j = 0; j < N; j++) {
if(DP[i - 1][j] == -1) {
DP[i][j] = -1;
}
else {
DP[i][j] = DP[i - 1][DP[i - 1][j]];
}
}
}
/*cout << "Centroid Parents\n";
for(long long i = 0; i < N; i++) {
cout << centroidParent[i] << " ";
}
cout << "\n";
cout << "distFromRoot\n";
for(long long i = 0; i < N; i++) {
cout << distFromRoot[i] << " ";
}
cout << "\n";
cout << "Normal parents\n";
for(long long i = 0; i < N; i++) {
cout << DP[0][i] << " ";
}
cout << "\n";
cout << "Binary lifting array\n";
for(long long i = 0; i < 20; i++) {
for(long long j = 0; j < N; j++) {
cout << DP[i][j] << " ";
}
cout << "\n";
}*/
}
long long LCA(long long x, long long y) {
if(depth[x] < depth[y])
swap(x, y);
long long diff = depth[x] - depth[y];
/*cout << "IN LCA\n";
cout << "x = " << x << ", y = " << y << ", diff = " << diff << "\n";
cout << "(1 << 2) = " << (1 << 2) << "\n";*/
for(long long i = 19; i >= 0; i--) {
if(diff >= (1 << i)) {
diff -= (1 << i);
x = DP[i][x];
}
}
//cout << "x = " << x << ", y = " << y << "\n";
if(x == y) {
//cout << "Answer = " << x << "\n";
return x;
}
for(long long i = 19; i >= 0; i--) {
if(DP[i][x] != DP[i][y]) {
x = DP[i][x];
y = DP[i][y];
}
}
//cout << "Answer = " << DP[0][x] << "\n";
return DP[0][x];
}
void Update(long long node) {
ans[node] = 0;
lastCnt[node] = cnt;
long long initial = node;
while(centroidParent[node] != node) {
node = centroidParent[node];
//cout << "Update function, updating " << initial << "\n";
//cout << "initial = " << initial << ", node = " << node << ", distance = " << distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)] << "\n";
if(lastCnt[node] != cnt) {
ans[node] = distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)];
lastCnt[node] = cnt;
}
else {
ans[node] = min(ans[node], distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)]);
}
//cout << "ans[node] = " << ans[node] << "\n";
}
}
long long Query2(long long node) {
if(lastCnt[node] == cnt)
return 0;
long long initial = node;
long long res = 1e15;
while(centroidParent[node] != node) {
node = centroidParent[node];
//cout << "Query function, querying " << initial << "\n";
//cout << "LCA(initial, node) = " << LCA(initial, node) << "\n";
//cout << "initial = " << initial << ", node = " << node << ", distance = " << distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)] << "\n";
if(lastCnt[node] == cnt) {
res = min(res, distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)] + ans[node]);
}
//cout << "res = " << res << "\n";
}
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
cnt++;
for(long long i = 0; i < S; i++) {
Update(X[i]);
}
/*cout << "Outputting ans array\n";
for(long long i = 0; i < N; i++) {
cout << ans[i] << " ";
}
cout << "\n";
cout << "Outputting lastCnt array\n";
for(long long i = 0; i < N; i++) {
cout << lastCnt[i] << " ";
}
cout << "\n";*/
long long res = 1e15;
for(long long i = 0; i < T; i++) {
res = min(res, Query2(Y[i]));
}
return res;
}