QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#629644 | #5148. Tree Distance | danielz | WA | 46ms | 58776kb | C++20 | 4.9kb | 2024-10-11 14:02:53 | 2024-10-11 14:02:53 |
Judging History
answer
#include "bits/stdc++.h"
using ll = long long;
const ll inf = 1e18;
using namespace std;
struct W {
int v; ll w;
friend istream& operator>>(istream& is, W &e) { return is >> e.v >> e.w; }
friend ostream& operator<<(ostream& os, W &e) { return os << e.v << ":" << e.w; }
bool operator==(const W o) const { return make_pair(v, w) == make_pair(o.v, o.w); }
operator int() const { return v; }
bool operator<(const W &o) const { return make_pair(v, w) < make_pair(o.v, o.w); }
bool operator<(int x) const { return v < x; }
};
template <int N, typename T = int>
struct Graph {
int n, m;
Graph() {}
Graph(int n, int m) : n(n), m(m) {}
Graph& init(int n, int m) { return this->n = n, this->m = m, *this; }
vector<T> g[N];
void add(int u, T e) { g[u].push_back(e); }
void u(int u, int v) {
if constexpr (is_same_v<T, int>) {
add(u, v);
add(v, u);
}
}
Graph& input() {
for (int i = 0; i < m; i++) {
int u; T v; cin >> u >> v;
g[u].push_back(v);
if constexpr (is_same_v<T, W>) g[v].push_back({u, v.w});
else g[v].push_back(u);
}
return *this;
}
};
using namespace std;
constexpr int lg(int x) {
return 31 - __builtin_clz(x);
}
template <int N, typename T = int>
struct ST {
static constexpr int K = lg(N) + 1;
function<T(T, T)> f;
T st[N + 1][K]{};
void build(T a[N]) {
for (int i = 0; i < N; i++) st[i][0] = a[i];
for (int k = 1; k < K; k++) for (int i = 0; i < N; i++) {
st[i][k] = st[i][k - 1];
if (int j = i + (1 << (k - 1)); j < N) st[i][k] = f(st[i][k], st[j][k - 1]);
}
}
T F(int l, int r) {
assert(l < r);
int k = lg(r - l);
return f(st[l][k], st[r - (1 << k)][k]);
}
};
template <int N, typename T = int>
struct Tree : Graph<N, T> {
int r, s[N], p[N];
ll d[N]{};
Tree() {}
Tree& init(int n) {
Graph<N, T>::init(n, n - 1);
fill(s, s + n + 1, 1);
return *this;
}
Tree& root(int x) { return r = p[x] = x, *this; }
int I[N], o[2 * N]{}, t = 0;
ST<2 * N> st{[&](int x, int y) { return d[x] < d[y] ? x : y; }};
int dfs(int x) {
for (T e : this->g[x]) {
o[I[x] = t++] = x;
if (e == p[x]) continue;
ll w = 1;
if constexpr (is_same_v<T, W>) w = e.w;
d[e] = d[p[e] = x] + w;
s[x] += dfs(e);
}
if (x == r) st.build(o);
return s[x];
}
int lca(int u, int v) {
if (I[u] > I[v]) swap(u, v);
return st.F(I[u], I[v] + 1);
}
ll D(int u, int v) {
return d[u] + d[v] - 2 * d[lca(u, v)];
}
int cr, cp[N]{}, rem[N]{};
vector<int> cg[N];
int sz(int x, int p = -1) {
s[x] = 0;
for (int y : this->g[x]) if (!rem[y] && y != p) s[x] += sz(y, x);
return ++s[x];
}
int decompose(int x, int n, int p = -1) {
for (int y : this->g[x]) if (!rem[y] && y != p) {
if (s[y] > n / 2) return decompose(y, n, x);
}
rem[x] = true;
for(int y : this->g[x]) if (!rem[y]) {
y = decompose(y, sz(y));
cg[cp[y] = x].push_back(y);
}
return x;
}
Tree& decompose() { return cr = decompose(r, sz(r)), *this; }
Tree& dfs() { return dfs(r), *this; }
Tree& input() { return Graph<N, T>::input(), *this; }
};
using namespace std;
template <int N, typename T = int>
struct SGT {
T a[2 * N], t0;
function<T(T, T)> f;
SGT& fn(function<T(T, T)> f, T x) { return this->f = f, t0 = x, *this; }
SGT& fill(T x) { return ::fill(a, a + 2 * N, x), *this; }
T query(int l, int r) {
T tl = t0, tr = t0;
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if (l & 1) tl = f(tl, a[l++]);
if (r & 1) tr = f(a[--r], tr);
}
return f(tl, tr);
}
void upd(int i, T x) {
for (a[i += N] = x; i >>= 1; ) a[i] = f(a[i << 1], a[i << 1|1]);
}
};
using namespace std;
const int N = 2e5 + 1;
struct P { int i; ll d; };
struct E { int u, v; ll w;
bool operator<(const E &o) const {
return v == o.v ? w > o.w : v < o.v;
}
};
vector<P> v[N];
SGT<2 * N, ll> sgt;
ll r[10 * N];
Tree<N, W> t;
int main() {
int n; cin >> n;
t.init(n).input().root(1).dfs().decompose();
for (int i = 1; i <= n; i++) {
int j = i;
while (j) {
v[j].push_back({i, t.D(i, j)});
j = t.cp[j];
}
}
vector<E> e;
for (int i = 1; i <= n; i++) {
vector<P> st;
for (auto [j, d] : v[i]) {
while (st.size() && st.back().d >= d) {
e.push_back({st.back().i, j, st.back().d + d});
st.pop_back();
}
if (st.size()) e.push_back({st.back().i, j, st.back().d + d});
st.push_back({j, d});
}
}
sgt.fn([](ll x, ll y) { return min(x, y); }, inf).fill(inf);
int q; cin >> q;
for (int i = 0; i < q; i++) {
r[i] = inf;
int u, v; cin >> u >> v;
for (auto [k, j, d] : e) if (u <= k && j <= v) r[i] = min(r[i], d);
cout << r[i] << endl;
}
for (int i = 0; i < q; i++) {
cout << (r[i] < inf ? r[i] : -1) << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 46ms
memory: 58776kb
input:
5 1 2 5 1 3 3 1 4 4 3 5 2 5 1 1 1 4 2 4 3 4 2 5
output:
1000000000000000000 3 7 7 2 -1 3 7 7 2
result:
wrong answer 1st numbers differ - expected: '-1', found: '1000000000000000000'