| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 364833 | Rainbowbunny | 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.
#include <iostream>
#include <algorithm>
#include <vector>
const long long INF = 1e17;
int time;
int tin[500005], tout[500005], depth[500005];
int SparseTable[21][1000005], Log[1000005];
long long DistanceFromRoot[500005];
std::vector <std::pair <int, int> > Adj[500005];
void DFS(int node, int p = -1)
{
SparseTable[0][time] = node;
tin[node] = time;
time++;
for(auto x : Adj[node])
{
if(x.first == p)
{
continue;
}
DistanceFromRoot[x.first] = DistanceFromRoot[node] + x.second;
depth[x.first] = depth[node] + 1;
DFS(x.first, node);
SparseTable[0][time] = node;
time++;
}
tout[node] = time;
}
int lower(int u, int v)
{
return depth[u] < depth[v] ? u : v;
}
void BuildLCA()
{
Log[0] = -1;
for(int i = 1; i <= 1000000; i++)
{
Log[i] = Log[i >> 1] + 1;
}
for(int i = 1; i <= 20; i++)
{
for(int j = 0; j + (1 << i) < 1000000; j++)
{
SparseTable[i][j] = lower(SparseTable[i - 1][j], SparseTable[i - 1][j + (1 << (i - 1))]);
}
}
}
int LCA(int u, int v)
{
int l = std::min(tin[u], tin[v]), r = std::max(tin[u], tin[v]);
return lower(SparseTable[Log[r - l + 1]][l], SparseTable[Log[r - l + 1]][r - (1 << Log[r - l + 1]) + 1]);
}
long long Distance(int u, int v)
{
return DistanceFromRoot[u] + DistanceFromRoot[v] - 2 * DistanceFromRoot[LCA(u, v)];
}
void Init(int N, int A[], int B[], int D[])
{
for(int i = 0; i < N - 1; i++)
{
Adj[A[i]].emplace_back(B[i], D[i]);
Adj[B[i]].emplace_back(A[i], D[i]);
}
DFS(0);
BuildLCA();
}
int stack[500005], top;
int color[500005];
long long dp[500005][2];
std::vector <int> VirtualAdj[500005];
long long Solve(int node, int p = -1)
{
long long ans = INF;
dp[node][0] = dp[node][1] = INF;
for(auto x : VirtualAdj[node])
{
if(x == p)
{
continue;
}
long long temp = Distance(x, node);
ans = std::min(ans, Solve(x, node));
if(dp[x][0] != INF)
{
dp[node][0] = std::min(dp[node][0], dp[x][0] + temp);
}
if(dp[x][1] != INF)
{
dp[node][1] = std::min(dp[node][1], dp[x][1] + temp);
}
}
if(color[node] == 1)
{
dp[node][0] = 0;
}
if(color[node] == 2)
{
dp[node][1] = 0;
}
ans = std::min(ans, dp[node][0] + dp[node][1]);
VirtualAdj[node].clear();
color[node] = 0;
return ans;
}
long long Query(int S, int X[], int T, int Y[])
{
std::vector <int> Vertex;
for(int i = 0; i < S; i++)
{
color[X[i]] = 1;
Vertex.push_back(X[i]);
}
for(int i = 0; i < T; i++)
{
if(color[Y[i]] == 1)
{
for(auto x : Vertex)
{
color[x] = 0;
}
return 0;
}
color[Y[i]] = 2;
Vertex.push_back(Y[i]);
}
std::sort(Vertex.begin(), Vertex.end(), [](int u, int v){
return tin[u] < tin[v];
});
top = 0;
stack[0] = 0;
for(auto x : Vertex)
{
if(x != 0)
{
int temp = LCA(x, stack[top]);
if(temp != stack[top])
{
while(tin[temp] < tin[stack[top - 1]])
{
VirtualAdj[stack[top - 1]].push_back(stack[top]);
VirtualAdj[stack[top]].push_back(stack[top - 1]);
top--;
}
if(tin[temp] > tin[stack[top - 1]])
{
VirtualAdj[temp].push_back(stack[top]);
VirtualAdj[stack[top]].push_back(temp);
stack[top] = temp;
}
else
{
VirtualAdj[stack[top]].push_back(temp);
VirtualAdj[temp].push_back(stack[top]);
top--;
}
}
top++;
stack[top] = x;
}
}
for(int i = 0; i + 1 <= top; i++)
{
VirtualAdj[stack[i]].push_back(stack[i + 1]);
VirtualAdj[stack[i + 1]].push_back(stack[i]);
}
return Solve(0);
}