#ifndef FACTORIES_H_
#define FACTORIES_H_
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include "factories.h"
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
#ifndef FACTORIES_H_
#define FACTORIES_H_
void Init(int N, int A[], int B[], int D[]);
long long Query(int S, int X[], int T, int Y[]);
#endif /* FACTORIES_H_ */
#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second;
using namespace std;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
const int MAXN = 5e5 + 5;
const long long inf = 1e18 + 3;
int numNode, numQuery, companyU, companyV, factoryU[MAXN], factoryV[MAXN], sz[MAXN];
bool del[MAXN];
long long best[MAXN];
vector<ii> adj[MAXN];
vector<pair<int, long long> > can[MAXN];
int getSize(int u, int par = 0){
sz[u] = 1;
for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
int v = x.fi, w = x.se;
sz[u] += getSize(v, u);
}
return sz[u];
}
int getCentroid(int sizeU, int u, int par = 0){
for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
int v = x.fi, w = x.se;
if (sz[v] > (sizeU >> 1)) return getCentroid(sizeU, v, u);
}
return u;
}
void addCan(int u, const int ¢roid, long long dist, int par = 0){
can[u].push_back({centroid, dist});
for(ii x: adj[u]) if (!del[x.fi] && x.fi != par) {
int v = x.fi, w = x.se;
addCan(v, centroid, dist + w, u);
}
}
void decomp(int u = 1){
int centroid = getCentroid(getSize(u), u);
del[centroid] = 1;
for(ii x: adj[centroid]) if (!del[x.fi]) {
int v = x.fi, w = x.se;
addCan(v, centroid, w);
}
for(ii x: adj[centroid]) if (!del[x.fi]){
int v = x.fi, w = x.se;
decomp(v);
}
}
void Init(int N, int A[], int B[], int D[]) {
numNode = N;
int u, v;
for(int i = 0; i < N - 1; i++){
u = A[i]; v = B[i];
u++; v++;
adj[u].push_back({v, D[i]});
adj[v].push_back({u, D[i]});
}
decomp();
for(int u = 1; u <= numNode; u++) can[u].push_back({u, 0});
memset(best, 0x3f, sizeof best);
}
void operation(int u, bool type){
best[u] = (type ? inf: 0);
for(pair<int, long long> x: can[u]){
int centroid = x.fi;
long long dist = x.se;
if (type) best[centroid] = inf;
else minimize(best[centroid], dist);
}
}
long long query(int u){
long long res = inf;
for(pair<int, long long> x: can[u]){
int centroid = x.fi;
long long dist = x.se;
minimize(res, dist + best[centroid]);
}
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; i++) X[i]++;
for(int i = 0; i < T; i++) Y[i]++;
for(int i = 0; i < S; i++) operation(X[i], 0);
long long res = inf;
for(int i = 0; i < T; i++) minimize(res, query(Y[i]));
for(int i = 0; i < S; i++) operation(X[i], 1);
return res;
}
#endif /* FACTORIES_H_ */
컴파일 시 표준 에러 (stderr) 메시지
factories.cpp:28: warning: "se" redefined
28 | #define se second;
|
factories.cpp:12: note: this is the location of the previous definition
12 | #define se second
|
/usr/include/c++/13/ranges: In constructor 'constexpr std::ranges::lazy_split_view<_Vp, _Pattern>::lazy_split_view(_Range&&, std::ranges::range_value_t<_Range>)':
factories.cpp:9:16: error: 'begin' is not a member of 'std::ranges::views'
9 | #define all(v) begin(v), end(v)
| ^~~~~
factories.cpp:9:16: note: suggested alternatives:
In file included from /usr/include/c++/13/string:53,
from /usr/include/c++/13/bits/locale_classes.h:40,
from /usr/include/c++/13/bits/ios_base.h:41,
from /usr/include/c++/13/ios:44,
from /usr/include/c++/13/ostream:40,
from /usr/include/c++/13/iostream:41,
from factories.cpp:4:
/usr/include/c++/13/bits/range_access.h:114:37: note: 'std::begin'
114 | template<typename _Tp> const _Tp* begin(const valarray<_Tp>&) noexcept;
| ^~~~~
In file included from /usr/include/c++/13/string_view:48,
from /usr/include/c++/13/bits/basic_string.h:47,
from /usr/include/c++/13/string:54:
/usr/include/c++/13/bits/ranges_base.h:489:44: note: 'std::ranges::__cust::begin'
489 | inline constexpr __cust_access::_Begin begin{};
| ^~~~~
In file included from /usr/include/c++/13/bits/stl_iterator_base_types.h:71,
from /usr/include/c++/13/bits/stl_construct.h:61,
from /usr/include/c++/13/bits/char_traits.h:57,
from /usr/include/c++/13/ios:42:
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note: 'std::ranges::__cust_access::begin'
984 | void begin(const auto&) = delete;
| ^~~~~
/usr/include/c++/13/ranges: In constructor 'constexpr std::ranges::split_view<_Vp, _Pattern>::split_view(_Range&&, std::ranges::range_value_t<_Range>)':
factories.cpp:9:16: error: 'begin' is not a member of 'std::ranges::views'
9 | #define all(v) begin(v), end(v)
| ^~~~~
factories.cpp:9:16: note: suggested alternatives:
/usr/include/c++/13/bits/range_access.h:114:37: note: 'std::begin'
114 | template<typename _Tp> const _Tp* begin(const valarray<_Tp>&) noexcept;
| ^~~~~
/usr/include/c++/13/bits/ranges_base.h:489:44: note: 'std::ranges::__cust::begin'
489 | inline constexpr __cust_access::_Begin begin{};
| ^~~~~
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note: 'std::ranges::__cust_access::begin'
984 | void begin(const auto&) = delete;
| ^~~~~
/usr/include/c++/13/ranges: At global scope:
factories.cpp:9:16: error: 'begin' is not a member of 'std::ranges::views'
9 | #define all(v) begin(v), end(v)
| ^~~~~
factories.cpp:9:16: note: suggested alternatives:
/usr/include/c++/13/bits/range_access.h:114:37: note: 'std::begin'
114 | template<typename _Tp> const _Tp* begin(const valarray<_Tp>&) noexcept;
| ^~~~~
/usr/include/c++/13/bits/ranges_base.h:489:44: note: 'std::ranges::__cust::begin'
489 | inline constexpr __cust_access::_Begin begin{};
| ^~~~~
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note: 'std::ranges::__cust_access::begin'
984 | void begin(const auto&) = delete;
| ^~~~~
/usr/include/c++/13/ranges: In member function 'constexpr auto std::ranges::views::_Common::operator()(_Range&&) const':
factories.cpp:9:16: error: 'begin' is not a member of 'std::ranges::views'
9 | #define all(v) begin(v), end(v)
| ^~~~~
factories.cpp:9:16: note: suggested alternatives:
/usr/include/c++/13/bits/range_access.h:114:37: note: 'std::begin'
114 | template<typename _Tp> const _Tp* begin(const valarray<_Tp>&) noexcept;
| ^~~~~
/usr/include/c++/13/bits/ranges_base.h:489:44: note: 'std::ranges::__cust::begin'
489 | inline constexpr __cust_access::_Begin begin{};
| ^~~~~
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note: 'std::ranges::__cust_access::begin'
984 | void begin(const auto&) = delete;
| ^~~~~