QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#548348 | #5148. Tree Distance | 000226 | WA | 1210ms | 190792kb | C++17 | 3.5kb | 2024-09-05 17:22:05 | 2024-09-05 17:22:05 |
Judging History
answer
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define Lep(i, l, r) for(int i = (l); i < (r); i ++)
//#define debug(...) fprintf (stderr, __VA_ARGS__)
#define debug(...)
using i64 = long long;
using ld = long double;
using LL = long long;
using ui64 = unsigned long long;
using ull = unsigned long long;
const int P = 998244353;
inline int mod(int x) { return x + (x >> 31 & P); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline void sub(int &x, int y) { x = mod(x - y); }
inline int add(int x, int y) { return mod (x + y - P); }
inline int dec(int x, int y) { return mod (x - y); }
template <typename T> inline void ckmin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline void ckmax(T &x, T y) { if (x < y) x = y; }
inline int power(int x, int k) {
int res = 1;
while(k) {
if (k & 1) res = 1ll * res * x % P;
x = 1ll * x * x % P; k >>= 1;
} return res;
}
const int N = 2e5 + 5;
int n;
vector<pair<int, int> > e[N];
vector<pair<int, i64> > lnk[N];
vector<pair<int, int> > qry[N * 5];
i64 ans[N * 5];
int sz[N], rt = 1, all, vis[N];
void findroot(int x, int fx) {
sz[x] = 1;
int mx = 0;
for (auto [y, w] : e[x]) if (y != fx && ! vis[y]) {
findroot(y, x);
sz[x] += sz[y];
ckmax(mx, sz[y]);
}
ckmax(mx, all - sz[x]);
if (mx * 2 <= all) rt = x;
}
void calc(int x) {
vector<pair<int, i64> > dis;
function<void(int, int, i64)> dfs = [&](int x, int fa, i64 curd) {
dis.emplace_back (x, curd);
for (auto [y, w] : e[x]) if (y != fa && ! vis[y]) {
dfs (y, x, curd + w);
}
};
dfs (x, 0, 0);
sort (dis.begin(), dis.end());
static int stk[N];
int top = 0;
for (int i = 0; i < dis.size(); i ++) {
auto [v, w] = dis[i];
while (top && dis[stk[top]].second > w) -- top;
if (top) {
lnk[v].emplace_back (dis[stk[top]].first, w + dis[stk[top]].second);
}
stk[++ top] = i;
}
top = 0;
for (int i = dis.size() - 1; i >= 0; i --) {
auto [v, w] = dis[i];
while (top && dis[stk[top]].second > w) -- top;
if (top) {
lnk[dis[stk[top]].first].emplace_back (v, w + dis[stk[top]].second);
}
stk[++ top] = i;
}
}
void Solve(int x) {
calc (x);
vis[x] = 1;
for (auto [y, w] : e[x]) if (! vis[y]) {
all = sz[y];
findroot(y, x);
Solve(rt);
}
}
#define lowbit(x) (x & -x)
i64 c[N];
void upd (int x, i64 y) {
for (; x; x -= lowbit(x)) ckmin(c[x], y);
}
i64 ask (int x) {
i64 res = 1e18 + 5;
for (; x <= n; x += lowbit(x)) ckmin (res, c[x]);
return res;
}
void solve() {
cin >> n;
lep (i, 1, n) c[i] = 1e18 + 5;
lep (i, 2, n) {
int x, y, w;
cin >> x >> y >> w;
e[x].push_back ( {y, w} );
e[y].push_back ( {x, w} );
}
rt = 1;
all = n;
findroot (1, 0);
findroot (rt, 0);
Solve (rt);
int q;
cin >> q;
lep (i, 1, q) {
int l, r;
cin >> l >> r;
qry[r].push_back ( {l, i} );
}
lep (r, 1, n) {
for (auto [pos, w] : lnk[r]) {
upd (pos, w);
//cerr << pos << ' ' << r << ' ' << w << endl;
}
for (auto [l, id] : qry[r]) {
ans[id] = ask (l);
}
}
lep (i, 1, q) if (ans[i] > 1e16) ans[i] = - 1;
lep (i, 1, q) cout << ans[i] << '\n';
lep (i, 1, n) e[i].clear();
lep (i, 1, n) lnk[i].clear();
lep (i, 1, q) qry[i].clear();
lep (i, 1, n) vis[i] = 0;
}
signed main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int Case = 1;
while (Case --) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 39652kb
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:
-1 3 7 7 2
result:
ok 5 number(s): "-1 3 7 7 2"
Test #2:
score: -100
Wrong Answer
time: 1210ms
memory: 190792kb
input:
199999 31581 23211 322548833 176307 196803 690953895 34430 82902 340232856 36716 77480 466375266 7512 88480 197594480 95680 61864 679567992 19572 14126 599247796 188006 110716 817477802 160165 184035 722372640 23173 188594 490365246 54801 56250 304741654 10103 45884 643490340 127469 154479 214399361...
output:
29573323 1178569098929 4088 65959 9935 7019193245 1136644395 4867978 328055210 55721881562 2062364707 339719 92126 92126 9935 138216269 8212187 9404444928 4453926 9935 1221317 114886 65959 1818252547 92126 97324 8367049186 26776689 5718199 15845903 92126 1162886184 365255209 92126 1221317 92126 9016...
result:
wrong answer 5th numbers differ - expected: '4366', found: '9935'