QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225058#5439. Meet in the MiddleluanmengleiWA 33ms56632kbC++176.2kb2023-10-23 22:01:552023-10-23 22:01:55

Judging History

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

  • [2023-10-23 22:01:55]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:56632kb
  • [2023-10-23 22:01:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
bool stB;
namespace SOL {

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

#define PASSED debug("PASSED (%s) LINE #%s", __FUNCTION__, __LINE__)

using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> void chkmax(T &x, L y) { if (x < y) x = y; }
template <typename T, typename L> void chkmin(T &x, L y) { if (y < x) x = y; }

const int N = 2e5 + 10;
const int M = 5e5 + 10;
int n, q;
i64 ans[M];

namespace LazySegmentTree {
	const int SEG_SIZE = N * 4;
	template<typename Node, typename Tag>
	struct LazyTagSegTree {
		#define lc (x * 2)
		#define rc (x * 2 + 1)
		#define mid ((l + r) >> 1)

		Node dat[SEG_SIZE];
		Tag tag[SEG_SIZE];

		void pull(int x) {
			dat[x] = dat[lc] + dat[rc];
		}

		void apply(int x, const Tag &t, int sze) {
			dat[x].apply(t, sze);
			tag[x].apply(t);
		}

		void push(int x, int l, int r) {
			if (tag[x]) {
				apply(lc, tag[x], mid - l + 1);
				apply(rc, tag[x], r - mid);
				tag[x].clear();
			}
		}

		void build(int x, int l, int r) {
			if (l == r) {
				dat[x].init(l);
				return;
			}
			build(lc, l, mid);
			build(rc, mid + 1, r);
			pull(x);
		}

		Node query(int x, int l, int r, int ql, int qr) {
			if (ql <= l && r <= qr) 
				return dat[x];
			push(x, l, r);
			if (ql <= mid && mid < qr)
				return query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr);
			else if (ql <= mid)
				return query(lc, l, mid, ql, qr);
			else
				return query(rc, mid + 1, r, ql, qr);
		}

		void modify(int x, int l, int r, int ql, int qr, const Tag &t) {
			if (ql > qr)
				return;
			if (ql <= l && r <= qr) 
				return apply(x, t, r - l + 1);
			push(x, l, r);
			if (ql <= mid)
				modify(lc, l, mid, ql, qr, t);
			if (mid < qr)
				modify(rc, mid + 1, r, ql, qr, t);
			pull(x);
		}

		void change(int x, int l, int r, int pos, const Node &k) {
			if (l == r)
				return dat[x] = k, void();
			push(x, l, r);
			if (pos <= mid)
				change(lc, l, mid, pos, k);
			else
				change(rc, mid + 1, r, pos, k);
			pull(x);
		} 

		#undef lc
		#undef rc
		#undef mid
	};
}

namespace Tree2 {
	vector<array<int, 2>> G[N];
	int lg2[N * 2], st[18][N * 2], in[N], out[N], cnt;
	i64 dep[N];

	void add_edge(int x, int y, int z) {
		G[x].push_back({ y, z });
		G[y].push_back({ x, z });
	}

	void dfs(int x, int fa) {
		in[x] = ++ cnt;
		st[0][cnt] = x;
		for (auto [y, z] : G[x]) if (y != fa) {
			dep[y] = dep[x] + z;
			dfs(y, x);
			st[0][++ cnt] = x;
		}
		out[x] = cnt;
	}

	int higher(int x, int y) {
		return dep[x] < dep[y] ? x : y;
	}

	void init_st() {
		for (int i = 2; i <= cnt; i ++)
			lg2[i] = lg2[i / 2] + 1;
		for (int i = 1; i <= lg2[cnt]; i ++)
			for (int j = 1; j + (1 << i) - 1 <= cnt; j ++)
				st[i][j] = higher(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
	}

	int get_lca(int x, int y) {
		x = in[x], y = in[y];
		if (x > y)
			swap(x, y);
		int k = lg2[y - x + 1];
		return higher(st[k][x], st[k][y - (1 << k) + 1]);
	} 

	i64 dist(int x, int y) {
		return dep[x] + dep[y] - 2 * dep[get_lca(x, y)];
	}

	void init() {
		dfs(1, 0);
		init_st();
	}
}

namespace Tree1 {
	vector<array<int, 2>> G[N];
	vector<array<int, 2>> req[N];
	int dfn[N], sze[N], cnt, id[N];
	i64 dep[N]; 

	void add_edge(int x, int y, int z) {
		G[x].push_back({ y, z });
		G[y].push_back({ x, z });
	}

	void add_query(int a, int b, int id) {
		req[a].push_back({ b, id });
	}

	void dfs1(int x, int fa) {
		dfn[x] = ++ cnt, sze[x] = 1, id[cnt] = x;
		for (auto [y, z] : G[x]) if (y != fa) {
			dep[y] = dep[x] + z;
			dfs1(y, x);
			sze[x] += sze[y];
		} 
	} 

	struct Tag {
		i64 add;

		void apply(const Tag &o) {
			add += o.add;
		}

		operator bool () {
			return add != 0;
		}

		void clear() {
			add = 0;
		}
	};

	struct Node {
		i64 diameter;
		array<pair<int, i64>, 2> pt;

		void init(int p) {
			diameter = dep[id[p]];
			pt[0] = pt[1] = { id[p], dep[id[p]] };
		}

		void apply(const Tag &o, int sze) {
			for (int i = 0; i < 2; i ++)
				pt[i].second += o.add;
		}
	};

	bool operator < (const Node &lhs, const Node &rhs) {
		return lhs.diameter < rhs.diameter;
	}

	Node operator + (const Node &lhs, const Node &rhs) {
		Node ret = max(lhs, rhs);
		for (int i = 0; i < 2; i ++) {
			for (int j = 0; j < 2; j ++) {
				auto [x, p] = lhs.pt[i];
				auto [y, q] = rhs.pt[j];
				Node cur;
				chkmax(ret, (Node) { p + q + Tree2::dist(x, y), { lhs.pt[i], rhs.pt[j] } });
			}
		}
		return ret;
	}

	LazySegmentTree::LazyTagSegTree<Node, Tag> segt;

	void dfs2(int x, int fa) {
		auto calc = [&](int p, pair<int, i64> pi) {
			return Tree2::dist(p, pi.first) + pi.second;
		};
		// debug("diameter point (%d, %lld) <=> (%d, %lld)", segt.dat[1].pt[0].first, segt.dat[1].pt[0].second, segt.dat[1].pt[1].first, segt.dat[1].pt[1].second);
		for (auto [b, id] : req[x])
			ans[id] = max(calc(b, segt.dat[1].pt[0]), calc(b, segt.dat[1].pt[1]));

		for (auto [y, z] : G[x]) if (y != fa) {
			segt.modify(1, 1, n, dfn[y], dfn[y] + sze[y] - 1, { -1 });
			segt.modify(1, 1, n, 1, dfn[y] - 1, { 1 });
			segt.modify(1, 1, n, dfn[y] + sze[y], n, { 1 });
			dfs2(y, x);
			segt.modify(1, 1, n, dfn[y], dfn[y] + sze[y] - 1, { 1 });
			segt.modify(1, 1, n, 1, dfn[y] - 1, { -1 });
			segt.modify(1, 1, n, dfn[y] + sze[y], n, { -1 });
		}
	}

	void work() {
		dfs1(1, 0);
		segt.build(1, 1, n);
		dfs2(1, 0);
	}
}

void solve() {
	cin >> n >> q;
	for (int i = 1, x, y, z; i < n; i ++) {
		cin >> x >> y >> z;
		Tree1::add_edge(x, y, z);
	}
	for (int i = 1, x, y, z; i < n; i ++) {
		cin >> x >> y >> z;
		Tree2::add_edge(x, y, z);
	}
	for (int i = 1, a, b; i <= q; i ++) {
		cin >> a >> b;
		Tree1::add_query(a, b, i);
	}
	Tree2::init();
	Tree1::work();
	for (int i = 1; i <= q; i ++)
		cout << ans[i] << "\n";
}

}
bool edB;
signed main() {
	// cerr << "Memory: " << (&stB - &edB) / 1024.0 / 1024.0 << "MB\n";
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	SOL::solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 53368kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

6
4
5
3

result:

ok 4 number(s): "6 4 5 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 53344kb

input:

2 1
1 2 1
1 2 1
1 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 3ms
memory: 53436kb

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 33ms
memory: 56632kb

input:

10000 50000
8101 5996 108427744
5996 7605 870838849
5996 5599 603303696
8101 3006 339377417
8101 6463 442516687
6463 5560 109174079
5560 4063 127596224
3006 1682 947915262
5996 1986 130416311
6463 5455 279771516
6463 2634 516688796
4063 3034 217886863
7605 5092 742375061
5599 2266 193804402
5092 140...

output:

639839190400
708764870726
606332097673
616399266562
554333476320
614123527211
657054971132
624986084755
635300298588
661355420061
716302912124
694442966976
690888045516
612317635685
639315307294
574060607034
602260092309
693892678971
595207826309
652846712638
663300051902
673650798270
541760421210
6...

result:

wrong answer 1st numbers differ - expected: '647838384844', found: '639839190400'