이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
author: Maksim1744
created: 09.04.2021 12:06:25
*/
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T>& v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T>& v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T>& v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "C:/C++ libs/print.cpp"
#else
#define show(...) 42
#define mclock 42
#define shows 42
#define debug if (false)
#endif
vector<int> lca_ind;
vector<vector<int>> lca_sparse;
vector<int> lca_p2;
vector<int> lca_depth;
vector<ll> lca_w_depth;
vector<int> tin, tout;
void build_lca_sparse(vector<vector<pair<int, int>>>& g, int root = 0) {
int n = g.size();
vector<int> euler;
lca_ind.resize(n);
lca_depth.assign(n, -1);
lca_w_depth.assign(n, 0);
tin.resize(n);
tout.resize(n);
int timer = 0;
function<void(int, int)> dfs = [&](int v, int depth) {
lca_ind[v] = euler.size();
euler.pb(v);
tin[v] = timer++;
lca_depth[v] = depth;
for (auto [k, w] : g[v]) {
if (lca_depth[k] == -1) {
lca_w_depth[k] = lca_w_depth[v] + w;
dfs(k, depth + 1);
euler.pb(v);
}
}
tout[v] = timer++;
};
dfs(root, 0);
int m = euler.size();
int log = 1;
while ((1 << log) < m)
++log;
lca_sparse.resize(log);
lca_sparse[0].resize(m);
lca_p2.resize(m + 1);
int pp2 = 0;
for (int i = 1; i < lca_p2.size(); ++i) {
if (1 << (pp2 + 1) <= i)
++pp2;
lca_p2[i] = pp2;
}
lca_p2[0] = 0;
for (int i = 0; i < m; ++i)
lca_sparse[0][i] = euler[i];
for (int i = 1; i < log; ++i) {
lca_sparse[i].assign(m, 0);
for (int j = 0; j < m - (1 << (i - 1)); ++j) {
int v1 = lca_sparse[i - 1][j], v2 = lca_sparse[i - 1][j + (1 << (i - 1))];
if (lca_depth[v1] < lca_depth[v2])
lca_sparse[i][j] = v1;
else
lca_sparse[i][j] = v2;
}
}
}
int get_lca(int u, int v) {
if (u == v)
return u;
u = lca_ind[u];
v = lca_ind[v];
if (u > v)
swap(u, v);
int v1 = lca_sparse[lca_p2[v - u + 1]][u], v2 = lca_sparse[lca_p2[v - u + 1]][v - (1 << lca_p2[v - u + 1]) + 1];
if (lca_depth[v1] < lca_depth[v2])
return v1;
else
return v2;
}
ll dist(int u, int v) {
return lca_w_depth[u] + lca_w_depth[v] - 2 * lca_w_depth[get_lca(u, v)];
}
vector<vector<pair<int, ll>>> g0;
vector<ll> dd;
void Init(int N, int A[], int B[], int D[]) {
int n = N;
g0.resize(n);
dd.resize(n);
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n; ++i) {
g[A[i]].eb(B[i], D[i]);
g[B[i]].eb(A[i], D[i]);
}
build_lca_sparse(g, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> vert;
for (int i = 0; i < S; ++i) {
vert.pb(X[i]);
}
for (int i = 0; i < T; ++i) {
vert.pb(Y[i]);
}
sort(vert.begin(), vert.end());
vert.erase(unique(vert.begin(), vert.end()), vert.end());
sort(vert.begin(), vert.end(), [&](int i, int j) {return tin[i] < tin[j];});
int sz = vert.size();
for (int i = 0; i < sz; ++i) {
vert.pb(get_lca(vert[i], vert[(i + 1) % sz]));
}
sort(vert.begin(), vert.end());
vert.erase(unique(vert.begin(), vert.end()), vert.end());
vector<pair<int, int>> ev;
for (int v : vert) {
ev.eb(tin[v], v);
ev.eb(tout[v], v);
}
sort(ev.begin(), ev.end());
show(ev);
vector<int> path;
ll ans = 1e18;
for (auto [tm, v] : ev) {
if (!path.empty() && path.back() == v) {
path.pop_back();
} else {
if (!path.empty()) {
int u = path.back();
ll d = dist(u, v);
g0[u].eb(v, d);
g0[v].eb(u, d);
}
path.pb(v);
}
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
for (int k : vert)
dd[k] = 1e18;
for (int i = 0; i < S; ++i) {
q.emplace(0, X[i]);
dd[X[i]] = 0;
}
show(vert);
show(q);
show(g0);
show(dd);
while (!q.empty()) {
auto [D, v] = q.top();
q.pop();
if (dd[v] < D) continue;
for (auto [k, w] : g0[v]) {
if (dd[k] > dd[v] + w) {
dd[k] = dd[v] + w;
q.emplace(dd[k], k);
}
}
}
show(dd);
for (int i = 0; i < T; ++i)
ans = min(ans, dd[Y[i]]);
for (int k : vert)
g0[k].clear();
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
factories.cpp: In function 'void build_lca_sparse(std::vector<std::vector<std::pair<int, int> > >&, int)':
factories.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 1; i < lca_p2.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
42 | #define show(...) 42
| ^~
factories.cpp:163:5: note: in expansion of macro 'show'
163 | show(ev);
| ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
42 | #define show(...) 42
| ^~
factories.cpp:188:5: note: in expansion of macro 'show'
188 | show(vert);
| ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
42 | #define show(...) 42
| ^~
factories.cpp:189:5: note: in expansion of macro 'show'
189 | show(q);
| ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
42 | #define show(...) 42
| ^~
factories.cpp:190:5: note: in expansion of macro 'show'
190 | show(g0);
| ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
42 | #define show(...) 42
| ^~
factories.cpp:191:5: note: in expansion of macro 'show'
191 | show(dd);
| ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
42 | #define show(...) 42
| ^~
factories.cpp:204:5: note: in expansion of macro 'show'
204 | show(dd);
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |