QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#646643 | #6404. Shuttle Tour | crimsonsunset | RE | 596ms | 70672kb | C++20 | 7.0kb | 2024-10-17 02:21:29 | 2024-10-17 02:21:31 |
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<int, int> d[20][(int)2e5];
//
//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 j = 1; j <= __lg(n); ++j)
// d[j][i] = {1e9, -1};
// }
// 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<vector<pair<int, int>>> d;
struct sparse_table {
sparse_table() {}
void build(vector<pair<int, int>> a) {
int n = a.size();
d.resize(21, vector<pair<int, int>>(2e5));
for (int i = 0; i < n; ++i)
d[0][i] = a[i];
// 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)
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: 100
Accepted
time: 4ms
memory: 37708kb
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: 0
Accepted
time: 539ms
memory: 70356kb
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:
17149847378 -1 26540740138 29613692754 21307948558 27003443184 11893407374 18332625722 20412196350 20281573062 29727468956 9593307160 9380710234 23682775470 16688997988 2856655228 14982588156 0 -1 9140136614 26193602866 22558599316 24807163344 19126284190 8533875940 7695830712 18079494744 0 27004673...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 596ms
memory: 70456kb
input:
50 200000 10010001110011101101101011010011100101101010111001 1 25 560163135 2 7 696374536 33 39 14485266 39 22 456690113 4 5 267811886 18 6 657680382 3 43 865617406 25 14 885515220 41 34 919525052 42 50 410634144 8 3 487403277 3 30 701549676 2 43 54223104 7 34 691078766 14 23 323352590 26 48 4936558...
output:
17177676326 31373486130 15290175638 8192974494 22734716092 27802380120 6315957348 0 15780401446 15929384564 26423899248 9639532596 21199366790 26413065782 -1 29063665908 29925313598 28651879288 17144176262 16526083688 28206620550 26873163342 14840246174 32414950818 29985336496 0 11937422088 11131990...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 541ms
memory: 70672kb
input:
50 200000 01011001001010000100001101100111011001101011101000 34 29 654100339 33 5 947063765 45 25 962067151 11 13 509130797 26 47 988757358 49 22 75267557 7 11 431530851 46 1 531969122 22 43 449891945 34 6 526679193 50 17 499004364 22 23 226725950 26 48 203414490 11 44 900725507 10 29 451714017 35 2...
output:
24080362406 0 0 21418182584 28358635244 28257750030 24520294678 21418182584 0 15335211126 28621468542 18664505530 19335499776 32374868794 23618866752 26801803500 24116134918 27676993638 30222353942 25612316674 20504702130 28400398734 29472795250 24400110084 20586186786 25612316674 0 30067400886 1297...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 10ms
memory: 37688kb
input:
2 10 01 1 2 340134039 2 1 2 1 1 2 1 2 1 2 2 1 1 1 2 2 2 2 1 2 2 2 2 1 1
output:
0 680268078 0 0 -1
result:
ok 5 number(s): "0 680268078 0 0 -1"
Test #6:
score: -100
Runtime Error
input:
200000 100 1100001001001101010000111111011011101010001011011011011010101111010001111010101100101001010000110100100011111010011100101010010001011010111100101110010000101010000100111100000011001100111101110011000011010011011011100101100111101010111101110111001111111010001010010000110110100000111000111...