QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#695590#5439. Meet in the MiddlegeorgeyucjrCompile Error//C++179.7kb2024-10-31 20:22:292024-10-31 20:22:29

Judging History

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

  • [2024-10-31 20:22:29]
  • 评测
  • [2024-10-31 20:22:29]
  • 提交

answer

# include<bits/stdc++.h>
using namespace std;

#ifndef georgeyucjr
#include <sys/mman.h>
#include <sys/stat.h>
#endif

using ll = long long;

# define rep(i, f, t, ...) for (int i = f, ##__VA_ARGS__; i <= t; ++i)
# define per(i, f, t, ...) for (int i = f, ##__VA_ARGS__; i >= t; --i)

# define SZ(x) int(x.size())
# define ALL(x) x.begin(), x.end()
# define FILEIO(fn) freopen(fn".in", "r", stdin), freopen(fn".out", "w", stdout)

// modify version
// static darry
template <typename T, int MXN, int MXM>
struct darry {
private:
	template <typename It>
	struct Rng {
		It b, e;
		It begin() const { return b; }
		It end() const { return e; }
		std ::uint32_t size() const {
			return (std ::uint32_t)(std ::distance(b, e));
		}
	};
	int n, bufcnt = 0;
	int head[MXN];
	T es[MXN];
	pair<int, T> buf[MXM];

public:
	void build() {
		partial_sum(head, head + n + 5, head);
		for (int _ = 0; _ < bufcnt; ++_) es[--head[buf[_].first]] = buf[_].second;
	}
	void init(int _n) { n = _n; }
	void clear() {
		memset(head, 0, sizeof(head[0]) * (n + 5));
		bufcnt = 0;
		n = 0;
	}
	template <typename... Args>
	void emplace(int u, Args &&...args) {
		buf[bufcnt++] = std::make_pair(u, T(std ::forward<Args>(args)...));
		++head[u];
	}
	Rng<T *> operator[](int u) { return {es + head[u], es + head[u + 1]}; }
	const Rng<const T *> operator[](int u) const {
		return {es + head[u], es + head[u + 1]};
	}
	std ::uint32_t size() const { return n; }
};

constexpr int N = 5e5 + 5;

int n, q, mcap, ceillog, fa1[N], dep1[N], dfn1[N], lst1[N], st1[20][N], fa2[N], dep2[N], dfn2[N], lst2[N], st2[20][N], Tm1 = 0, Tm2 = 0, id1[N], id2[N], sz1[N], sz2[N], ans[N];
ll td1[N], td2[N];
darry<pair<int, int>, N, N * 2> G1, G2;
darry<pair<int, int>, N, N> V;

inline int LCA_op1(const int &u, const int &v) { return dep1[u] < dep1[v] ? u : v; }
inline int LCA_op2(const int &u, const int &v) { return dep2[u] < dep2[v] ? u : v; }

void dfs1(int u, int _f) {
	sz1[u] = 1;
	fa1[u] = _f;
	dep1[u] = dep1[_f] + 1;
	dfn1[u] = ++Tm1;
	lst1[Tm1] = _f;
	id1[Tm1] = u;
	for (auto [v, w] : G1[u])
		if (v != _f)
			td1[v] = td1[u] + w, dfs1(v, u), sz1[u] += sz1[v];
}


void init_LCA1() {
	int lg = 31 - __builtin_clz(n);
	copy(lst1 + 1, lst1 + n + 1, st1[0] + 1);
	rep(i, 1, lg)
	rep(j, 1, n + 1 - (1 << i))
	st1[i][j] = LCA_op1(st1[i - 1][j], st1[i - 1][j + (1 << (i - 1))]);
}

int LCA1(int x, int y) {
	if (x == y) return x;
	int u = dfn1[x], v = dfn1[y];
	if (u > v) swap(u, v);
	int lg = 31 - __builtin_clz(v - u++);
	return LCA_op1(st1[lg][u], st1[lg][v - (1 << lg) + 1]);
}

int dist1(int u, int v) {
	return td1[u] + td1[v] - td1[LCA1(u, v)] * 2;
}

void dfs2(int u, int _f) {
	fa2[u] = _f;
	sz2[u] = 1;
	dep2[u] = dep2[_f] + 1;
	dfn2[u] = ++Tm2;
	lst2[Tm2] = _f;
	id2[Tm2] = u;
	for (auto [v, w] : G2[u])
		if (v != _f)
			td2[v] = td2[u] + w, dfs2(v, u), sz2[u] += sz2[v];
}


void init_LCA2() {
	int lg = 31 - __builtin_clz(n);
	copy(lst2 + 1, lst2 + n + 1, st2[0] + 1);
	rep(i, 1, lg)
	rep(j, 1, n + 1 - (1 << i))
	st2[i][j] = LCA_op2(st2[i - 1][j], st2[i - 1][j + (1 << (i - 1))]);
}

int LCA2(int x, int y) {
	if (x == y) return x;
	int u = dfn2[x], v = dfn2[y];
	if (u > v) swap(u, v);
	int lg = 31 - __builtin_clz(v - u++);
	return LCA_op2(st2[lg][u], st2[lg][v - (1 << lg) + 1]);
}

int dist2(int u, int v) {
	return td2[u] + td2[v] - td2[LCA2(u, v)] * 2;
}

struct infonode {
	int u, v;
	ll v1, v2, dia;
	void o() const {
		cerr << "u = " << u << ", v = " << v << ", v1 = " << v1 << ", v2 = " << v2 << ", dia = " << dia << "\n";
	}
} seg[1 << 20 | 5];

infonode operator + (const infonode &x, const infonode & y) {
	infonode ans = x.dia > y.dia ? x : y;
	{
		infonode t;
		t.u = x.u, t.v = y.u; t.v1 = x.v1, t.v2 = y.v1;
		t.dia = dist2(t.u, t.v) + t.v1 + t.v2;
		if (t.dia > ans.dia) ans = t;
	}
	{
		infonode t;
		t.u = x.u, t.v = y.v; t.v1 = x.v1, t.v2 = y.v2;
		t.dia = dist2(t.u, t.v) + t.v1 + t.v2;
		if (t.dia > ans.dia) ans = t;
	}
	{
		infonode t;
		t.u = x.v, t.v = y.u; t.v1 = x.v2, t.v2 = y.v1;
		t.dia = dist2(t.u, t.v) + t.v1 + t.v2;
		if (t.dia > ans.dia) ans = t;
	}
	{
		infonode t;
		t.u = x.v, t.v = y.v; t.v1 = x.v2, t.v2 = y.v2;
		t.dia = dist2(t.u, t.v) + t.v1 + t.v2;
		if (t.dia > ans.dia) ans = t;
	}
	// x.o(), y.o(), ans.o();
	return ans;
}

using tagnode = ll;
infonode operator + (const infonode &x, const tagnode & y) {
	// x.o(); cerr << y << "\n";
	infonode res = x;
	res.v1 += y;
	res.v2 += y;
	if (x.u != x.v) res.dia += 2 * y;
	// res.o();
	return res;
}

tagnode lt[1 << 20 | 5];

void pu(int i) {seg[i] = seg[i * 2] + seg[i * 2 + 1];}
void addtag(int i, ll v) {seg[i] = seg[i] + v, lt[i] += v;}
void pd(int i) {if (lt[i])addtag(i * 2, lt[i]), addtag(i * 2 + 1, lt[i]), lt[i] = 0;}
void build_zkw(int i = 1, int l = 1, int r = n) {
	if (l == r) return seg[i].u = seg[i].v = id1[i], seg[i].v1 = seg[i].v2 = dist1(1, id1[i]), seg[i].dia = 0, void();
	int mid = (l + r) >> 1; build_zkw(i * 2, l, mid), build_zkw(i * 2 + 1, mid + 1, r), pu(i);
}
void change(int ql, int qr, ll v, int i = 1, int l = 1, int r = n) {
	if (l == ql && r == qr)return addtag(i, v);
	int mid = (l + r) >> 1; pd(i); if (qr <= mid)change(ql, qr, v, i * 2, l, mid);
	else if (ql > mid)change(ql, qr, v, i * 2 + 1, mid + 1, r);
	else change(ql, mid, v, i * 2, l, mid), change(mid + 1, qr, v, i * 2 + 1, mid + 1, r);
	pu(i);
}
infonode qall() {return seg[1];}

// bool bup[1 << 20 | 5];

// void pu(int i) {
// 	if ((!bup[i]) || (!bup[i * 2])) { [[unlikely]]
// 		return ;
// 	}
// 	if (!bup[i * 2 + 1])
// 		seg[i] = seg[i * 2];
// 	else
// 		seg[i] = seg[i * 2] + seg[i * 2 + 1];
// }

// void build_zkw() {
// 	ceillog = 1;
// 	while((1 << ceillog) < n) ceillog <<= 1;
// 	mcap = 1 << ceillog;
// 	fill(lt + 1, lt + mcap * 2 + 1, 0);
// 	rep(i, 0, mcap + n - 1) bup[i] = true;
// 	rep(i, 0, n - 1) seg[i + mcap].u = seg[i + mcap].v = id1[i + 1], seg[i + mcap].v1 = seg[i + mcap].v2 = dist1(1, id1[i + 1]), seg[i + mcap].dia = 0;
// 	for (int len = mcap / 2, cnt = (n + 1) / 2, w = 2; len; len >>= 1, cnt = (cnt + 1) / 2, w <<= 1)
// 		rep(i, len, len + cnt - 1) pu(i);
// }

// inline int clg(int x) {
// 	int ans = 0; while((1 << ans) < x) ++ans; return ans;
// }

// void addtag(int i, ll v) {
// 	if (!bup[i]) return ;
// 	seg[i] = seg[i] + v, lt[i] += v;
// }

// void pushdown(int i) {
// 	if (lt[i]) {
// 		addtag(i * 2 + 0, lt[i]);
// 		addtag(i * 2 + 1, lt[i]);
// 		lt[i] = 0;
// 	}
// }

// void change(int l, int r, ll v) {
// 	// cerr << "l = " << l << ", r = " << r << ", v = " << v << "\n";
// 	--l, --r;
// 	if (l == r) return addtag(l + mcap, v);
// 	assert(0 <= l && l < n);
// 	assert(0 <= r && r < n);
// 	l += mcap, r += mcap;
// 	int j = clg(l ^ r) - 1;
// 	for (int d = ceillog; d > j; --d) pushdown(l >> d);
// 	for (int d = j; d >= 0; --d) pushdown(l >> d), pushdown(r >> d);
// 	addtag(l, v), addtag(r, v);
// 	// cerr << "----\n";
// 	while(l >> 1 < r << 1) {
// 		if (!(l & 1)) addtag(l + 1, v);
// 		l >>= 1; pu(l);
// 		// seg[l] = seg[l * 2] + seg[l * 2 + 1];
// 		if (r & 1) addtag(r - 1, v);
// 		r >>= 1; pu(r);
// 		// seg[r] = seg[r * 2] + seg[r * 2 + 1];
// 	}
// 	while(l >>= 1) seg[l] = seg[l * 2] + seg[l * 2 + 1];
// }

// infonode qall() { return seg[1]; }

void dfs3(int u, int _f) {
	// cerr << "u = " << u << ", f = " << _f << "\n";
	infonode x = qall();
	for (auto [fr, sc] : V[u]) {
		ans[sc] = max(dist2(x.u, fr) + x.v1, dist2(x.v, fr) + x.v2);
		if (sc == 3 || sc == 4)
			// cerr << "1 : " << x.u << " " << fr << " " << x.v1 << " " << x.v << " " << fr << " " << x.v2 << "\n";
	}
	// cerr << "---\n";
	for (auto [v, w] : G1[u])
		if (v != _f)
		{
			change(dfn1[v], dfn1[v] + sz1[v] - 1, -2 * w);
			change(1, n, +w);
			dfs3(v, u);
			change(1, n, -w);
			change(dfn1[v], dfn1[v] + sz1[v] - 1, +2 * w);
		}
}

signed main() {
	// FILEIO("move");
#ifndef georgeyucjr
	struct stat st;
	fstat(0, &st);
	auto c = (char *)mmap(nullptr, st.st_size, 1, 2, 0, 0);

	unsigned _rd_a[0x10000], _read_value, _read_flag;
	auto _read_init = [&]() {
		memset(_rd_a, -1, 0x40000);
		for (int i = 48; i <= 57; i++)
			for (int j = 48; j <= 57; j++)
				_rd_a[(i << 8) + j] = (j - 48) * 10 + (i - 48);
	};
	auto read_int_t = [&]() -> int {
		_read_value = _read_flag = 0;
		c += _read_flag = *c == 45;
		while (~_rd_a[*(uint16_t *)(c)])
			_read_value = _read_value * 100 + _rd_a[*(uint16_t *)(c)], c += 2;
		if (*c >= '0') _read_value = _read_value * 10 + ((*c++) ^ 48);
		return _read_flag ? -_read_value : _read_value;
	};
	auto read_uint_t = [&]() -> uint32_t {
		_read_value = 0;
		while (~_rd_a[*(uint16_t *)(c)])
			_read_value = _read_value * 100 + _rd_a[*(uint16_t *)(c)], c += 2;
		if (*c >= '0') _read_value = _read_value * 10 + ((*c++) ^ 48);
		return _read_value;
	};
	_read_init();
#else
	cin.tie(0)->sync_with_stdio(0);
	uint64_t c = 0;
	// uint32_t read_uint_t() {
	auto read_uint_t = [&]() -> uint32_t {
		uint32_t x;
		cin >> x;
		return x;
	};
	auto read_int_t = [&]() -> int32_t {
		int32_t x;
		cin >> x;
		return x;
	};
#endif
	n = read_uint_t(), ++c, q = read_uint_t(), ++c;
	rep(i, 1, n - 1, u, v, w) u = read_uint_t(), ++c, v = read_uint_t(), ++c, w = read_uint_t(), ++c, G1.emplace(u, v, w), G1.emplace(v, u, w);
	rep(i, 1, n - 1, u, v, w) u = read_uint_t(), ++c, v = read_uint_t(), ++c, w = read_uint_t(), ++c, G2.emplace(u, v, w), G2.emplace(v, u, w);
	G1.build(); dfs1(1, 0); init_LCA1();
	G2.build(); dfs2(1, 0); init_LCA2();
	build_zkw(); rep(i, 1, q, x, y) x = read_uint_t(), ++c, y = read_uint_t(), ++c, V.emplace(x, y, i); V.build();
	dfs3(1, 0); rep(i, 1, q) cout << ans[i] << " "; cout << "\n";
}

详细

answer.code: In function ‘void dfs3(int, int)’:
answer.code:275:9: error: expected primary-expression before ‘}’ token
  275 |         }
      |         ^