QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#129126 | #6404. Shuttle Tour | Energy_is_not_over | AC ✓ | 2923ms | 49536kb | C++17 | 9.6kb | 2023-07-21 22:13:04 | 2023-07-21 22:13:07 |
Judging History
answer
//
// Created by Barichek on 20.07.2023 13:20:07
//
#include <bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
using namespace std;
using namespace atcoder;
const int max_n = 200222, inf = 1000111222;
const int max_lev = 18;
int ok_sz[max_n], H[max_n], ok_son[max_n];
string s;
vector<int> order, start, fin;
pair<int, int> get_val(int v) {
if (s[v] == '0') {
return {-1, -1};
}
return {v, v};
}
pair<int, int> merge_p(pair<int, int> a, pair<int, int> b) {
if (a.first == -1) {
return b;
}
if (b.first == -1) {
return a;
}
int x = (H[a.first] < H[b.first]) ? a.first : b.first;
int y = (H[a.second] > H[b.second]) ? a.second : b.second;
return {x, y};
}
pair<int, int> identity() {
return {-1, -1};
}
class tree {
public:
int tin[max_n], tout[max_n];
long long h[max_n]; // h[root] = 0
int p[max_lev][max_n];
void init(int n, vector<pair<int, int>> g[], int root = 0) {
curt = -1;
for (int i = 0; i < max_lev; ++i) {
p[i][root] = root;
}
dfs(root, g);
get_all_p(n);
}
bool is_ancestor(int u, int v) const {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) const {
if (is_ancestor(u, v)) {
return u;
}
for (int i = max_lev - 1; i >= 0; --i) {
if (!is_ancestor(p[i][u], v)) {
u = p[i][u];
}
}
return p[0][u];
}
int get_dist(int u, int v) const {
const int lc = lca(u, v);
return h[u] + h[v] - 2 * h[lc];
}
int get_up(int v, int dist) const {
for (int i = max_lev - 1; i >= 0; --i) {
if (get_bit(dist, i)) {
v = p[i][v];
}
}
return v;
}
protected:
void dfs(int v, vector<pair<int, int>> g[]) {
tin[v] = ++curt;
for (auto [to, w] : g[v]) {
if (to == p[0][v]) {
continue;
}
++ok_sz[v];
p[0][to] = v;
h[to] = h[v] + w;
H[to] = H[v] + 1;
ok_son[v] = to;
dfs(to, g);
}
tout[v] = curt;
}
void get_all_p(int n) {
for (int lev = 1; lev < max_lev; ++lev) {
for (int i = 0; i < n; ++i) {
p[lev][i] = p[lev - 1][p[lev - 1][i]];
}
}
}
static bool get_bit(int mask, int pos) {
return (mask >> pos) & 1;
}
int curt;
} t;
long long ans;
vector<int> build_virtual_tree(const tree &t, vector<int> vs) {
auto cmp_by_tin = [&t](int a, int b) {
return t.tin[a] < t.tin[b];
};
sort(vs.begin(), vs.end(), cmp_by_tin);
vs.erase(unique(vs.begin(), vs.end()), vs.end());
for (int i = 0, sz = vs.size(); i + 1 < sz; ++i) {
vs.push_back(t.lca(vs[i], vs[i + 1]));
}
sort(vs.begin(), vs.end(), cmp_by_tin);
vs.erase(unique(vs.begin(), vs.end()), vs.end());
const int n = vs.size();
vector<int> st;
ans = 0;
for (int v : vs) {
while (!st.empty() && !t.is_ancestor(st.back(), v)) {
st.pop_back();
}
if (!st.empty()) {
ans += abs(t.h[v] - t.h[st.back()]);
}
st.push_back(v);
}
return vs;
}
int n, q, num_path[max_n];
vector<pair<int, int>> g[max_n];
vector<vector<int>> paths;
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q >> s;
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u;
--v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
t.init(n, g);
vector<segtree<pair<int, int>, merge_p, identity>> sts;
for (int i = 0; i < n; ++i) {
if (ok_sz[i] == 0) {
vector<int> path;
int v = i;
while (true) {
path.push_back(v);
if (!v) {
break;
}
if (ok_sz[t.p[0][v]] == 1 || ok_son[t.p[0][v]] == v) {
v = t.p[0][v];
} else {
break;
}
}
sort(path.begin(), path.end());
start.push_back(order.size());
for (int v : path) {
order.push_back(v);
num_path[v] = paths.size();
}
fin.push_back(order.size() - 1);
paths.push_back(path);
vector<pair<int, int>> init(path.size());
for (int i = 0; i < path.size(); ++i) {
init[i] = get_val(path[i]);
}
sts.emplace_back(init);
}
}
while (q--) {
int tp;
cin >> tp;
if (tp == 1) {
int x;
cin >> x;
--x;
s[x] ^= '0' ^ '1';
const int pos = lower_bound(paths[num_path[x]].begin(), paths[num_path[x]].end(), x) - paths[num_path[x]].begin();
sts[num_path[x]].set(pos, get_val(x));
} else {
int l, r;
cin >> l >> r;
--l;
--r;
vector<int> all;
for (int i = 0; i < paths.size(); ++i) {
auto it1 = lower_bound(paths[i].begin(), paths[i].end(), l);
auto it2 = upper_bound(it1, paths[i].end(), r);
if (it1 < it2) {
auto p = sts[i].prod(it1 - paths[i].begin(), it2 - paths[i].begin());
if (p.first != -1) {
all.push_back(p.first);
}
if (p.second != -1) {
all.push_back(p.second);
}
}
}
if (all.empty()) {
cout << "-1\n";
continue;
}
build_virtual_tree(t, all);
cout << 2 * ans << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 27224kb
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: 162ms
memory: 26952kb
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: 156ms
memory: 27416kb
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: 159ms
memory: 26120kb
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: 0ms
memory: 26196kb
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: 0
Accepted
time: 110ms
memory: 48616kb
input:
200000 100 1100001001001101010000111111011011101010001011011011011010101111010001111010101100101001010000110100100011111010011100101010010001011010111100101110010000101010000100111100000011001100111101110011000011010011011011100101100111101010111101110111001111111010001010010000110110100000111000111...
output:
187263442365796 187267199881816 187176203274470 187269896250018 187239740690858 186974761323092 187257776119514 187269896250018 187035239640930 186911636122472 187263030332128 187121605387264 187264313877130 187263442365796 187269896250018 187249588971104 187263442365796 187263442365796 187264313877...
result:
ok 50 numbers
Test #7:
score: 0
Accepted
time: 94ms
memory: 49536kb
input:
200000 100 1000100001000101011000010111101000110001110111010000000010100100001110001110011001001011000010001000101111000111000100111101111111011111101101011110010101110000011011000101010000101110000100101000101110011111110000010011010010001001010001101000001111001001011111110100100011011100010100101...
output:
187406582272754 187713357625510 187713357625510 187710409039730 187708440524170 187705546874918 187675370061160 187696435101958 187704004975728 187708440524170 187708440524170 187490194913408 186797006090958 187708440524170 187708440524170 187694259450196 187691068337432 187699562335668 187708440524...
result:
ok 50 numbers
Test #8:
score: 0
Accepted
time: 93ms
memory: 41576kb
input:
200000 100 1101110101111010101100101110111101001010101100011111011010101101001011000101011011110110110001000000110000100110101010001011100110100101010110001111000100011010101011100011111010111001011110110001001010000001010100000000100010010000110100101010000111010100100111001011101001000011010101011...
output:
187071935465024 186902015424650 186944515923806 187083386398370 187083386398370 186176053533638 187210565613960 186840136921858 187059112646348 186963648681914 187157614978100 187171857507720 186687953621656 187037985042418 184267618052908 185811051686090 186716949587794 186666528269428 186754258305...
result:
ok 50 numbers
Test #9:
score: 0
Accepted
time: 2895ms
memory: 41504kb
input:
200000 200000 1010011001010010101000001000111111110110111100000011000110010101000001101110111000100011010101100011001011101100010100000010100000100110100001000111010000011001010111001001000000111001100110010100101010111000000000011110101110010101110110110101100001011001101010101001000010000010000000...
output:
185874943612396 186901189463748 185325592077116 187007806200644 185723936146376 186683200699722 186830061692652 186256265895174 186860903405924 186810412385682 186744028102060 186994420108608 186831837842360 180459525430870 186966649455016 186952309712742 185810351127924 186849618327982 186494273101...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 2923ms
memory: 41216kb
input:
200000 200000 1101100101010001011001101010110111010000001100111000100010001111101101110111001101000001101011010000001110101101001010011000001011000101010111001101100100101001100111010001101010011100101100010110000011110101101011000011101101010111101000000111100100011101000110011100011000010010001011...
output:
187559700459682 187535810670694 187366757549978 187509694959444 186405180245408 187572993046976 186802217032708 186278525122374 187171989295434 187404069323808 187366390326582 184670301024044 186230793287498 187530780070456 187597311483370 187406310330638 187384636670170 187047338416520 187544270920...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 2920ms
memory: 41764kb
input:
200000 200000 0011111000111101101011111111000010101011010000100000110110010110010000011010101011101001100001001001000001100110010100101101001111000111010011110100000100000001111111000001000101000011110001101101111000101001100010010011001101100111110000110001100001100011110011001100100010000010001101...
output:
187057082821034 187050489592834 185798962075874 186490497612254 185547643085476 185839649755426 186731725449660 186845143722558 186446910671932 186830913714546 186903848544526 186827856700414 187012840145598 187030896936824 186738571374322 186338959389628 186977751482606 187075649881228 186978915850...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 1ms
memory: 24352kb
input:
1 3 0 2 1 1 1 1 2 1 1
output:
-1 0
result:
ok 2 number(s): "-1 0"
Test #13:
score: 0
Accepted
time: 2ms
memory: 27076kb
input:
7 2 0001100 1 2 1 2 3 10 3 4 100 4 5 1000 3 6 10000 6 7 100000 2 1 7 2 2 6
output:
2000 2000
result:
ok 2 number(s): "2000 2000"