QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548751 | #6404. Shuttle Tour | pandapythoner# | RE | 0ms | 0kb | C++23 | 4.8kb | 2024-09-05 20:36:52 | 2024-09-05 20:36:52 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)
struct SGT {
int n;
vector<array<ll, 50>> mx;
vector<array<ll, 50>> mn;
void upd(int v) {
if (mx[v + v][0] == -1) {
mx[v] = mx[v + v + 1];
mn[v] = mn[v + v + 1];
} else if (mx[v + v + 1][0] == -1) {
mx[v] = mx[v + v];
mn[v] = mn[v + v];
} else {
rep(i, 50) {
mx[v][i] = max(mx[v + v][i], mx[v + v + 1][i]);
mn[v][i] = min(mn[v + v][i], mn[v + v + 1][i]);
}
}
}
void build(vector<array<ll, 50>> a) {
n = 1;
while (n < len(a)) n *= 2;
mx.resize(n * 2);
mn.resize(n * 2);
for (int i = 0; i < len(a); i += 1) {
mx[i + n] = a[i];
mn[i + n] = a[i];
}
for (int i = n - 1; i >= 1; i -= 1) upd(i);
}
void set(int i, array<ll, 50> x) {
i += n;
mx[i] = mn[i] = x;
for (i /= 2; i >= 1; i /= 2) upd(i);
}
ll get(int l, int r) {
l += n;
r += n + 1;
array<ll, 50> rmn, rmx;
rmn.fill(-1);
rmx.fill(-1);
while (l < r) {
if (l & 1) {
if (rmn[0] == -1) {
rmn = mn[l];
rmx = mx[l];
} else if (mn[l][0] != -1) {
rep(i, 50) {
rmn[i] = min(rmn[i], mn[l][i]);
rmx[i] = max(rmx[i], mx[l][i]);
}
}
l += 1;
}
if (r & 1) {
r -= 1;
if (rmn[0] == -1) {
rmn = mn[r];
rmx = mx[r];
} else if (mn[r][0] != -1) {
rep(i, 50) {
rmn[i] = min(rmn[i], mn[r][i]);
rmx[i] = max(rmx[i], mx[r][i]);
}
}
}
l /= 2;
r /= 2;
}
if (rmn[0] == -1) {
return -1;
}
ll rs = 0;
rep(i, 50) rs += rmx[i] - rmn[i];
rs *= 2;
return rs;
}
};
struct edge {
int to;
ll w;
};
int n, q;
vector<int> status;
vector<vector<edge>> g;
vector<ll> depth, dir;
int cur_way;
vector<int> my_way;
array<ll, 50> start;
vector<array<ll, 50>> values, to_build;
SGT sgt;
array<ll, 50> get(int i) {
if (status[i] == 0) {
array<ll, 50> rs;
rs.fill(-1);
return rs;
}
return values[i];
}
void dfs1(int v, int p, int way) {
my_way[v] = way;
depth[v] = 0;
int last_way = way;
rep(i, len(g[v])) {
auto [to, w] = g[v][i];
if (to == p) continue;
if (last_way == -1) {
last_way = cur_way++;
dir[to] = -1;
dfs1(to, v, last_way);
start[last_way] = depth[to] + w;
} else {
dir[to] = 1;
if (last_way == way) {
dir[to] = dir[v];
}
dfs1(to, v, last_way);
last_way = -1;
}
if (to == g[v][0].to) depth[v] = depth[to] + w;;
}
}
void dfs2(int v, int p, array<ll, 50> cur) {
values[v] = cur;
for (auto [to, w] : g[v]) {
if (to == p) continue;
auto new_cur = cur;
new_cur[my_way[to]] += w * dir[to];
dfs2(to, v, new_cur);
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> q;
status.resize(n);
rep(i, n) {
char c;
cin >> c;
status[i] = c - '0';
}
g.assign(n, vector<edge>());
rep(i, n - 1) {
int u, v;
cin >> u >> v;
ll w;
cin >> w;
--u;
--v;
g[u].push_back(edge{ v, w });
g[v].push_back(edge{ u, w });
}
cur_way = 0;
depth.resize(n);
my_way.resize(n);
dir.resize(n);
start.fill(0);
dfs1(0, -1, cur_way++);
assert(cur_way <= 50);
values.resize(n);
dir[0] = 1;
dfs2(0, -1, start);
rep(v, n) rep(i, 50) assert(values[v][i] >= 0);
to_build.resize(n);
rep(i, n) to_build[i] = get(i);
sgt.build(to_build);
rep(itr, q) {
int t;
cin >> t;
if (t == 1) {
int i;
cin >> i; --i;
status[i] ^= 1;
sgt.set(i, get(i));
} else {
int l, r;
cin >> l >> r;
--l;
--r;
cout << sgt.get(l, r) << "\n";
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
5 6 10110 1 2 1 1 3 10 2 4 100 3 5 1000 2 1 5 1 3 2 1 5 2 2 4 2 5 5 2 1 1