QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693267#5439. Meet in the MiddleArgharizaWA 0ms29956kbC++174.4kb2024-10-31 15:51:012024-10-31 15:51:04

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 15:51:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:29956kb
  • [2024-10-31 15:51:01]
  • 提交

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;
}

详细

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'