QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#646608 | #6404. Shuttle Tour | crimsonsunset | WA | 617ms | 37628kb | C++20 | 5.9kb | 2024-10-17 01:55:09 | 2024-10-17 01:55:10 |
Judging History
answer
#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()
struct seg_tree {
vector<pair<pair<int, int>, pair<int, int>>> tree;
int n;
seg_tree(int n) : n(n) {
tree.resize(4 * n, {{0, -1},{2e5 + 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},
{2e5, -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},{2e5 + 1, -1}});
}
};
struct sparse_table {
vector<vector<pair<int, int>>> d;
sparse_table() {}
void build(vector<pair<int, int>> a) {
int n = a.size();
d.resize(__lg(n) + 1, a);
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)
return 0;
++r;
int t = __lg(r - l);
return min(d[t][l], d[t][r - (1 << t)]).ss;
}
} sp;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<vector<pair<int, int>>> gr(n);
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});
}
vector<array<int, 3>> que(q);
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);
vector<ll> dist(n);
int timer = 0;
auto dfs = [&](auto self, int v, int p, ll d, int dp) -> void {
tin[v] = timer++;
dist[v] = d;
depth[v] = dp;
for (auto [u, c]: gr[v])
if (u != p)
self(self, u, v, d + c, dp + 1);
};
dfs(dfs, 0, -1, 0, 0);
vector<pair<int, int>> ord(n);
for (int i = 0; i < n; ++i)
ord[i] = {depth[i], i};
sp.build(ord);
vector<vector<int>> need(q);
string t = s;
for (int i = 0; i < n; ++i)
if (gr[i].size() == 1) {
s = t;
timer = 0;
dfs(dfs, i, -1, 0, 0);
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;
dfs(dfs, 0, -1, 0, 0);
vector<vector<int>> cmp(n);
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(root, 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(st.back(), 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: 100
Accepted
time: 0ms
memory: 3564kb
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 0
result:
ok 5 number(s): "222 202 0 -1 0"
Test #2:
score: -100
Wrong Answer
time: 617ms
memory: 37628kb
input:
50 200000 00100100100001101010110100000111100011101110011010 14 47 940241413 11 43 331483591 37 38 496247070 47 46 832459694 7 15 16479291 1 30 402388666 30 8 513064064 46 50 739311480 5 4 761894947 32 41 631669659 17 24 715786564 35 20 763151642 32 33 492466005 39 11 186023146 9 7 805081251 3 42 25...
output:
58088272740 -1 218548187252 183588305976 96648233970 224152391198 37344989894 69687983654 117095070890 87804767338 250954379068 14199938456 15483751926 122320004948 28112904812 2856655228 53256236240 0 -1 3510859036 122290635630 52663552924 166986549606 60786734642 29752084442 30291060664 1079522693...
result:
wrong answer 1st numbers differ - expected: '17149847378', found: '58088272740'