이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "Yes" << en
#define no cout << "No" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))
using namespace std;
class Sparse{
int n;
vector<ll> a;
vector<vector<int> > lookup;
public:
Sparse(){}
Sparse(const vector<ll>& A){ Assign(A); }
void Assign(const vector<ll>& A){
n = A.size();
a = A;
lookup.assign(n, vector<int>(lg(n)+1, -1));
for (int i = 0; i < n; i++)
lookup[i][0] = i;
for (int d = 1; d <= lg(n); d++){
for (int i = 0; i < n; i++){
if (i + (1 << (d-1)) < n){
int x = lookup[i][d-1], y = lookup[i+(1<<(d-1))][d-1];
lookup[i][d] = (!~y || a[x] < a[y] ? x : y);
}
}
}
}
int query(int l, int r) const {
int d = highpow(r-l+1);
int x = lookup[l][lg(d)], y = lookup[r-d+1][lg(d)];
return (a[x] < a[y] ? x : y);
}
};
const ll LINF = 1e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, dist[mxN], in[mxN], out[mxN];
vector<array<ll, 2> > g[mxN];
vector<ll> e, d;
Sparse E;
int Lca(int u, int v){
if (in[u] > in[v]) swap(u, v);
return e[E.query(in[u], out[v])];
}
ll Dist(int u, int v){
int s = Lca(u, v);
return dist[u] + dist[v] - 2*dist[s];
}
void Euler(int s = 0, int p = -1, ll dep = 0){
dist[s] = dep;
in[s] = e.size();
e.pb(s); d.pb(dep);
for (auto [u, w] : g[s]){
if (u^p){
Euler(u, s, dep+w);
e.pb(s); d.pb(dep);
}
}
out[s] = e.size();
e.pb(s); d.pb(dep);
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for (int i = 0; i < n-1; i++){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
Euler();
E.Assign(d);
}
void Build(int N, int A[], vector<array<int, 2> >& e, vector<ll>& d){
for (int i = 0; i < N; i++){
e.pb({in[A[i]], A[i]});
e.pb({out[A[i]], A[i]});
}
sort(all(e));
for (auto [i, s] : e) d.pb(dist[s]);
}
int BSL(int x, const vector<array<int, 2> >& a){
int l = 0, r = a.size()-1, ans = a.size();
while (l <= r){
int k = (l + r + 1)>>1;
if (a[k][0] >= x){
ans = k;
r = k - 1;
}
else l = k + 1;
}
return ans;
}
int BSR(int x, const vector<array<int, 2> >& a){
int l = 0, r = a.size()-1, ans = -1;
while (l <= r){
int k = (l + r + 1)>>1;
if (a[k][0] <= x){
ans = k;
l = k + 1;
}
else r = k - 1;
}
return ans;
}
long long Query(int S, int X[], int T, int Y[]){
vector<array<int, 2> > eX, eY;
vector<ll> dX, dY;
Build(S, X, eX, dX);
Build(T, Y, eY, dY);
Sparse sX(dX), sY(dY);
vector<int> a;
for (auto [i, s] : eX) a.pb(i);
for (auto [i, s] : eY) a.pb(i);
sort(all(a));
vector<int> A;
for (int i = 0; i < a.size()-1; i++)
A.pb(e[E.query(a[i], a[i+1])]);
ll ans = LINF;
for (int s : A){
int i = BSL(in[s], eX), j = BSR(out[s], eX);
if (i > j) continue;
int u = eX[sX.query(i, j)][1];
i = BSL(in[s], eY); j = BSR(out[s], eY);
if (i > j) continue;
int v = eY[sY.query(i, j)][1];
smin(ans, Dist(u, v));
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
factories.cpp: In function 'void Build(int, int*, std::vector<std::array<int, 2> >&, std::vector<long long int>&)':
factories.cpp:115:22: warning: narrowing conversion of 'in[(*(A + ((sizetype)(((long unsigned int)i) * 4))))]' from 'long long int' to 'int' [-Wnarrowing]
115 | e.pb({in[A[i]], A[i]});
| ~~~~~~~^
factories.cpp:116:23: warning: narrowing conversion of 'out[(*(A + ((sizetype)(((long unsigned int)i) * 4))))]' from 'long long int' to 'int' [-Wnarrowing]
116 | e.pb({out[A[i]], A[i]});
| ~~~~~~~~^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:162:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for (int i = 0; i < a.size()-1; i++)
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |