QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#225058 | #5439. Meet in the Middle | luanmenglei | WA | 33ms | 56632kb | C++17 | 6.2kb | 2023-10-23 22:01:55 | 2023-10-23 22:01:55 |
Judging History
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'