이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 5;
const ll INF = 1e18;
int top = 0 , timer = 0;
vector<pair<int , ll>> edge[N];
int tin[N] , depth[N] , color[N];
ll d[N];
int up[N][21];
vector<int> Virtual[N];
int st[N];
ll dp[N][3];
void dfs(int u , int p = -1)
{
tin[u] = ++timer;
for (auto adj : edge[u])
{
int v = adj.first;
ll w = adj.second;
if (v == p) continue;
up[v][0] = u;
for (int j = 1 ; j <= 20 ; ++j) up[v][j] = up[up[v][j - 1]][j - 1];
depth[v] = depth[u] + 1;
d[v] = d[u] + w;
dfs(v , u);
}
}
int lca(int u , int v)
{
if (depth[u] < depth[v]) swap(u , v);
for (int j = 20 ; j >= 0 ; --j)
{
if (depth[u] - (1 << j) >= depth[v])
{
u = up[u][j];
}
}
if (u == v) return u;
for (int j = 20 ; j >= 0 ; --j)
{
if (up[u][j] != up[v][j])
{
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
ll dist(int u , int v)
{
return d[u] + d[v] - 2 * d[lca(u , v)];
}
void Init(int n , int a[] , int b[] , int d[])
{
for (int i = 0 ; i < n - 1 ; ++i)
{
++a[i] , ++b[i];
edge[a[i]].push_back({b[i] , d[i]});
edge[b[i]].push_back({a[i] , d[i]});
}
dfs(1);
}
bool cmp(int x , int y)
{
return tin[x] < tin[y];
}
ll dfs2(int u , int p = -1)
{
ll ans = INF;
dp[u][1] = dp[u][2] = INF;
for (int v : Virtual[u])
{
if (v == p) continue;
ans = min(ans , dfs2(v , u));
int cur = dist(u , v);
dp[u][1] = min(dp[u][1] , dp[v][1] + cur);
dp[u][2] = min(dp[u][2] , dp[v][2] + cur);
}
dp[u][color[u]] = 0;
ans = min(ans , dp[u][1] + dp[u][2]);
Virtual[u].clear();
color[u] = 0;
return ans;
}
long long Query(int s , int x[] , int t , int y[])
{
vector<int> a;
for (int i = 0 ; i < s ; ++i)
{
++x[i];
color[x[i]] = 1;
a.push_back(x[i]);
}
for (int i = 0 ; i < t ; ++i)
{
++y[i];
color[y[i]] = 2;
a.push_back(y[i]);
}
sort(a.begin() , a.end() , cmp);
st[1] = 1;
top = 1;
for (int x : a)
{
if (x != 1)
{
int tmp = lca(x , st[top]);
if (tmp != st[top])
{
while(tin[tmp] < tin[st[top - 1]])
{
Virtual[st[top]].push_back(st[top - 1]);
Virtual[st[top - 1]].push_back(st[top]);
--top;
}
Virtual[tmp].push_back(st[top]);
Virtual[st[top]].push_back(tmp);
if (tin[tmp] > tin[st[top - 1]])
{
st[top] = tmp;
}
else
{
--top;
}
}
++top;
st[top] = x;
}
}
for (int i = 1 ; i < top ; ++i)
{
Virtual[st[i]].push_back(st[i + 1]);
Virtual[st[i + 1]].push_back(st[i]);
}
return dfs2(1);
}
/*
int main()
{
freopen(".inp","r",stdin);
freopen(".out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n , q;
cin >> n >> q;
int a[n] , b[n] , d[n];
for (int i = 0 ; i < n - 1 ; ++i) cin >> a[i] >> b[i] >> d[i];
Init(n , a , b , d);
// return 0;
while(q--)
{
int s , t;
cin >> s >> t;
int x[s] , y[t];
for (int i = 0 ; i < s ; ++i) cin >> x[i];
for (int i = 0 ; i < t ; ++i) cin >> y[i];
cout << Query(s , x , t , y) << "\n";
}
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |