| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 469632 | Lam_lai_cuoc_doi | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
void read(T &x)
{
x = 0;
register int c;
while ((c = getchar()) && (c > '9' || c < '0'))
;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
}
constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr ll Inf = 1e17 + 7;
struct Path
{
int v, type;
ll w;
} a[N];
int n, m, in[N], beg[N];
int cnt[N], en[N], l(0), par[N];
ll dep[N], ans;
vector<pair<int, ll>> adj[N];
void dfs(int v, int p = -1)
{
cnt[v] = 1;
for (auto i : adj[v])
if (i.first != p)
{
par[i.first] = v;
dep[i.first] = dep[v] + i.second;
dfs(i.first, v);
cnt[v] += cnt[i.first];
}
}
void hld(int v)
{
in[v] = l;
if (!beg[in[v]])
beg[in[v]] = v;
pair<int, int> ans({0, 0});
for (auto i : adj[v])
if (i.first != par[v])
ans = max(ans, make_pair(cnt[i.first], i.first));
if (ans.first != 0)
{
hld(ans.second);
for (auto i : adj[v])
if (i.first != par[v] && i.first != ans.second)
{
++l;
hld(i.first);
}
}
}
void Init(int nn, vector<int> a, vector<int> b, vector<int> d)
{
n = nn;
for (int i = 0; i < n - 1; ++i)
{
adj[a[i] + 1].emplace_back(b[i] + 1, d[i]);
adj[b[i] + 1].emplace_back(a[i] + 1, d[i]);
}
l = 1;
dfs(1);
hld(1);
}
void GetPath(int v, int type)
{
ll w = dep[v];
while (v)
{
++m;
a[m].v = v;
a[m].type = type;
a[m].w = w;
v = par[beg[in[v]]];
}
}
void Cal(int x, int y)
{
sort(a + x, a + y + 1, [&](const Path &a, const Path &b)
{ return dep[a.v] < dep[b.v]; });
ll minn[2] = {Inf, Inf};
for (int i = y; i >= x; --i)
{
ans = min(ans, a[i].w + minn[a[i].type ^ 1] - 2 * dep[a[i].v]);
minn[a[i].type] = min(minn[a[i].type], a[i].w);
}
}
ll Query(int s, vector<int> u, int t, vector<int> v)
{
m = 0;
ans = Inf;
for (int i = 0; i < s; ++i)
GetPath(u[i] + 1, 1);
for (int i = 0; i < t; ++i)
GetPath(v[i] + 1, 0);
sort(a + 1, a + m + 1, [&](const Path &a, const Path &b)
{ return in[a.v] < in[b.v]; });
for (int i = 1, j = 1; i <= m; ++i)
{
while (j <= m && in[a[i].v] == in[a[j].v])
++j;
Cal(i, j - 1);
i = j - 1;
}
return ans;
}