QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#646650 | #6404. Shuttle Tour | crimsonsunset | WA | 0ms | 14144kb | C++20 | 7.3kb | 2024-10-17 02:29:54 | 2024-10-17 02:29:54 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops,inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//pair<pair<int, int>, pair<int, int>> tree[(int)8e5];
//
//struct seg_tree {
// int n;
//
// seg_tree(int n) : n(n) {
// fill(tree, tree + 4 * n, make_pair(make_pair(0, -1), make_pair(1e9 + 1, -1)));
// }
//
// pair<pair<int, int>, pair<int, int>> get(int v, int tl, int tr, int l, int r) {
// if (r < tl || tr < l)
// return {{0, -1}, {1e9, -1}};
// if (l <= tl && tr <= r)
// return tree[v];
// int tm = (tl + tr) / 2;
// auto x = get(v * 2, tl, tm, l, r), y = get(v * 2 + 1, tm + 1, tr, l, r);
// return {max(x.ff, y.ff), min(x.ss, y.ss)};
// }
//
// void upd(int v, int tl, int tr, int pos, pair<pair<int, int>, pair<int, int>> x) {
// if (tl == tr) {
// tree[v] = x;
// return;
// }
// int tm = (tl + tr) / 2;
// if (pos <= tm)
// upd(v * 2, tl, tm, pos, x);
// else
// upd(v * 2 + 1, tm + 1, tr, pos, x);
// tree[v].ff = max(tree[v * 2].ff, tree[v * 2 + 1].ff);
// tree[v].ss = min(tree[v * 2].ss, tree[v * 2 + 1].ss);
// }
//
// pair<int, int> get(int l, int r) {
// auto x = get(1, 0, n - 1, l, r);
// return {x.ff.ss, x.ss.ss};
// }
//
// void upd(int v, int val) {
// if (val != -1)
// upd(1, 0, n - 1, v, {{val, v}, {val, v}});
// else
// upd(1, 0, n - 1, v, {{0, -1},{1e9 + 1, -1}});
// }
//};
//
pair<pair<int, int>, pair<int, int>> tr[(int) 4e5];
struct seg_tree {
int n;
seg_tree() = default;
seg_tree(int n) : n(n) {
fill(tr, tr + 2 * n, make_pair(make_pair(0, -1), make_pair(1e9 + 1, -1)));
}
void upd(int k, pair<pair<int, int>, pair<int, int>> x) {
for (tr[k += n] = x;
k > 1; k >>= 1, tr[k] = {max(tr[k << 1].ff, tr[k << 1 | 1].ff), min(tr[k << 1].ss, tr[k << 1 | 1].ss)});
}
pair<int, int> get(int l, int r) {
pair<pair<int, int>, pair<int, int>> ans = {{0, -1},{1e9 + 1, -1}};
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) ans = {max(tr[l++].ff, ans.ff), min(tr[l++].ss, ans.ss)};
if (~r & 1) ans = {max(tr[r--].ff, ans.ff), min(tr[r--].ss, ans.ss)};
}
return {ans.ff.ss, ans.ss.ss};
}
void upd(int v, int val) {
if (val != -1)
upd(v, {{val, v}, {val, v}});
else
upd(v, {{0, -1},{1e9 + 1, -1}});
}
};
pair<int, int> d[22][(int) 4e5];
struct sparse_table {
sparse_table() {}
void build(vector<pair<int, int>> a) {
int n = a.size();
for (int i = 0; i < n; ++i)
d[0][i] = a[i];
for (int i = 1; i <= __lg(n); ++i)
for (int j = 0; j + (1 << (i - 1)) < n; ++j)
d[i][j] = min(d[i - 1][j], d[i - 1][j + (1 << (i - 1))]);
}
int get(int l, int r) {
if (l > r)
swap(l, r);
++r;
int t = __lg(r - l);
return min(d[t][l], d[t][r - (1 << t)]).ss;
}
} sp;
vector<pair<int, int>> gr[(int) 2e5];
vector<int> cmp[(int) 2e5], need[(int) 2e5];
array<int, 3> que[(int) 2e5];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
string s;
cin >> s;
for (int i = 1, u, v, c; i < n; ++i) {
cin >> u >> v >> c;
--u, --v;
gr[u].push_back({v, c});
gr[v].push_back({u, c});
}
for (int i = 0; i < q; ++i) {
cin >> que[i][0];
if (que[i][0] == 1)
cin >> que[i][1], --que[i][1];
else
cin >> que[i][1] >> que[i][2], --que[i][1], --que[i][2];
}
vector<int> tin(n), depth(n), pos(n);
vector<ll> dist(n);
int timer = 0;
vector<pair<int, int>> ord;
auto dfs = [&](auto self, int v, int p, ll d, int dp) -> void {
tin[v] = timer++;
pos[v] = ord.size();
dist[v] = d;
depth[v] = dp;
ord.push_back({depth[v], v});
for (auto [u, c]: gr[v])
if (u != p) {
self(self, u, v, d + c, dp + 1);
ord.push_back({depth[v], v});
}
};
dfs(dfs, 0, -1, 0, 0);
sp.build(ord);
auto dfs2 = [&](auto self, int v, int p) -> void {
tin[v] = timer++;
for (auto [u, c]: gr[v])
if (u != p)
self(self, u, v);
};
string t = s;
for (int i = 0; i < n; ++i)
if (gr[i].size() <= 1) {
s = t;
timer = 0;
dfs2(dfs2, i, -1);
seg_tree tr(n);
for (int j = 0; j < n; ++j)
if (s[j] == '1')
tr.upd(j, tin[j]);
for (int j = 0; j < q; ++j) {
if (que[j][0] == 1) {
if (s[que[j][1]] == '1') {
tr.upd(que[j][1], -1);
s[que[j][1]] = '0';
} else {
tr.upd(que[j][1], tin[que[j][1]]);
s[que[j][1]] = '1';
}
} else {
auto x = tr.get(que[j][1], que[j][2]);
need[j].push_back(x.ff);
need[j].push_back(x.ss);
}
}
}
timer = 0;
dfs2(dfs2, 0, -1);
for (int i = 0; i < q; ++i) {
if (need[i].size()) {
sort(all(need[i]));
need[i].resize(unique(all(need[i])) - need[i].begin());
if (need[i][0] == -1) {
cout << -1 << '\n';
continue;
}
vector<pair<int, int>> v;
for (int j = 0; j < need[i].size(); ++j)
v.push_back({tin[need[i][j]], need[i][j]});
sort(all(v));
int root = v[0].ss;
for (int j = 1; j < v.size(); ++j)
root = sp.get(pos[root], pos[v[j].ss]);
vector<int> st = {root}, vr = {root};
for (int j = 0; j < v.size(); ++j) {
int last = -1;
if (v[j].ss == st.back())
continue;
int an = sp.get(pos[st.back()], pos[v[j].ss]);
while (!st.empty() && depth[st.back()] > depth[an]) {
last = st.back();
st.pop_back();
}
if (an == st.back()) {
cmp[st.back()].push_back(v[j].ss);
} else {
cmp[st.back()].pop_back();
cmp[st.back()].push_back(an);
cmp[an].push_back(last);
cmp[an].push_back(v[j].ss);
st.push_back(an);
vr.push_back(an);
}
st.push_back(v[j].ss);
vr.push_back(v[j].ss);
}
ll ans = 0;
for (int j: vr)
for (int u: cmp[j])
ans += dist[u] - dist[j];
for (int j: vr)
cmp[j].clear();
cout << ans * 2 << '\n';
}
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 14144kb
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
output:
222 202 0 -1 -1
result:
wrong answer 5th numbers differ - expected: '0', found: '-1'