QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#693267 | #5439. Meet in the Middle | Arghariza | WA | 0ms | 29956kb | C++17 | 4.4kb | 2024-10-31 15:51:01 | 2024-10-31 15:51:04 |
Judging History
answer
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;
typedef long long ll;
typedef pair<int, ll> pi;
bool Mbe;
const int N = 1e5 + 5;
const int M = 5e5 + 5;
int n, m, dfc;
int id[N], rid[N], sz[N], g[N][25], id2[N];
ll da[N], db[N], ans[M];
vector<pi> T1[N], T2[N], q[N];
void clr() {
dfc = 0;
F (i, 1, n) {
q[i].clear();
T1[i].clear();
T2[i].clear();
}
}
void dfs1(int u, int f) {
rid[id[u] = ++dfc] = u, sz[u] = 1;
for (pi p : T1[u]) {
int v = p.fi, w = p.se;
if (v == f) {
continue;
}
da[v] = da[u] + w;
dfs1(v, u), sz[u] += sz[v];
}
}
void dfs2(int u, int f) {
id2[u] = ++dfc, g[dfc][0] = f;
for (pi p : T2[u]) {
int v = p.fi, w = p.se;
if (v == f) {
continue;
}
db[v] = db[u] + w;
dfs2(v, u);
}
}
int gt(int u, int v) {
return id2[u] < id2[v] ? u : v;
}
int lca(int u, int v) {
if (u == v) {
return u;
}
u = id2[u], v = id2[v];
if (u > v) swap(u, v); u++;
int len = __lg(v - u + 1);
return gt(g[u][len], g[v - (1 << len) + 1][len]);
}
ll dis(int u, int v) {
return db[u] + db[v] - 2 * db[lca(u, v)];
}
struct SEG {
struct Info {
int u, v;
ll cu, cv, d;
Info () { u = v = cu = cv = d = 0; }
Info (int _u, int _v, ll _cu, ll _cv, ll _d) :
u(_u), v(_v), cu(_cu), cv(_cv), d(_d) { }
bool operator < (const Info &r) const {
return d < r.d;
}
Info operator + (const Info &r) const {
pi t[4] = { mp(u, cu), mp(v, cv), mp(r.u, r.cu), mp(r.v, r.cv) };
Info res;
F (i, 0, 3) {
F (j, 0, i - 1) {
if (t[i].fi && t[j].fi) {
res = max(res, Info(t[i].fi, t[j].fi, t[i].se, t[j].se, dis(t[i].fi, t[j].fi) + t[i].se + t[j].se));
}
}
}
return res;
}
Info operator + (const ll &r) const {
return Info(u, v, cu + r, cv + r, d + 2 * r);
}
} tr[N << 2];
ll lz[N << 2];
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
void pup(int x) {
tr[x] = tr[ls] + tr[rs];
}
void plz(int x, ll c) {
tr[x] = tr[x] + c;
lz[x] += c;
}
void pdn(int x) {
if (lz[x]) {
plz(ls, lz[x]);
plz(rs, lz[x]);
lz[x] = 0;
}
}
void bld(int l, int r, int x) {
lz[x] = 0;
if (l == r) {
int u = rid[l];
tr[x] = Info(u, u, da[u], da[u], 2 * da[u]);
return;
}
bld(l, mid, ls);
bld(mid + 1, r, rs);
pup(x);
}
void add(int l, int r, int s, int t, ll c, int x) {
if (s <= l && r <= t) {
plz(x, c);
return;
}
pdn(x);
if (s <= mid) {
add(l, mid, s, t, c, ls);
}
if (t > mid) {
add(mid + 1, r, s, t, c, rs);
}
pup(x);
}
ll qry(int l, int r, int p, int x) {
if (l == r) {
return tr[x].cu;
}
pdn(x);
if (p <= mid) {
return qry(l, mid, p, ls);
} else {
return qry(mid + 1, r, p, rs);
}
}
void b() {
bld(1, n, 1);
}
void a(int l, int r, ll w) {
add(1, n, l, r, w, 1);
}
Info q() {
return tr[1];
}
} T;
void dfs3(int u, int f) {
auto res = T.q();
for (pi p : q[u]) {
int b = p.fi, id = p.se;
ans[id] = max(dis(res.u, b) + res.cu, dis(res.v, b) + res.cv);
}
for (pi p : T1[u]) {
int v = p.fi, w = p.se;
if (v == f) {
continue;
}
T.a(1, n, w);
T.a(id[v], id[v] + sz[v] - 1, -2 * w);
dfs3(v, u);
T.a(1, n, -w);
T.a(id[v], id[v] + sz[v] - 1, 2 * w);
}
}
void solve() {
cin >> n;
F (i, 1, n - 1) {
int u, v, w;
cin >> u >> v >> w;
T1[u].eb(v, w);
T1[v].eb(u, w);
}
F (i, 1, n - 1) {
int u, v, w;
cin >> u >> v >> w;
T2[u].eb(v, w);
T2[v].eb(u, w);
}
cin >> m;
F (i, 1, m) {
int u, v;
cin >> u >> v;
q[u].eb(v, i);
}
dfs1(1, 0);
dfc = 0;
dfs2(1, 0);
F (j, 1, __lg(n)) {
F (i, 1, n - (1 << j) + 1) {
g[i][j] = gt(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
}
}
T.b();
dfs3(1, 0);
F (i, 1, m) {
cout << ans[i] << '\n';
}
clr();
}
bool Med;
int main() {
// FIO("move");
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
int T = 1;
// cin >> T;
T = 1;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 29956kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
12
result:
wrong answer 1st numbers differ - expected: '6', found: '12'