QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199294 | #6404. Shuttle Tour | UrgantTeam | RE | 0ms | 0kb | C++23 | 5.7kb | 2023-10-04 04:45:13 | 2023-10-04 04:45:14 |
answer
#include<bits/stdc++.h>
using namespace std;
struct pt {
int to, w, node;
};
typedef long long ll;
int const maxn = 2e5 + 5, K = 55;
string s;
int numb[maxn], tmp = 1;
ll h[maxn], ans;
vector < pair < int, int > > g[maxn];
pair < int, int > dp[(1 << 20)][K];
pair < int, int > f[K];
vector < pt > G[K];
int ok[maxn], good[maxn];
int lst[maxn];
void dfs(int v, int p, int cur) {
assert(cur < K);
int flag = 1;
lst[v] = p;
numb[v] = cur;
for (auto [u, w] : g[v]) {
if (u == p) continue;
h[u] = h[v] + w;
if (flag) dfs(u, v, cur), flag = 0;
else {
G[cur].push_back({tmp, w, v});
tmp++;
dfs(u, v, tmp - 1);
}
}
}
inline pair < int, int > merge(pair < int, int > a, pair < int, int > b) {
if (a.first == -1 || (b.first != -1 && h[a.first] > h[b.first])) a.first = b.first;
if (a.second == -1 || (a.second != -1 && h[a.second] < h[b.second])) a.second = b.second;
return a;
}
void build(int i, int l, int r) {
if (r - l == 1) {
for (int j = 0; j < tmp; j++) {
dp[i][j] = {-1, -1};
}
if (s[l] == '1') dp[i][numb[l]] = {l, l};
} else {
int m = (r + l) / 2;
build(2 * i + 1, l, m);
build(2 * i + 2, m, r);
for (int j = 0; j < tmp; j++) {
dp[i][j] = merge(dp[2 * i + 1][j], dp[2 * i + 2][j]);
}
}
}
void update(int i, int l, int r, int lq) {
if (r - l == 1) {
assert(l == lq);
if (s[lq] == '1') s[lq] = '0';
else s[lq] = '1';
for (int j = 0; j < tmp; j++) {
dp[i][j] = {-1, -1};
}
if (s[l] == '1') dp[i][numb[l]] = {l, l};
} else {
int m = (r + l) / 2;
if (lq < m) update(2 * i + 1, l, m, lq);
else update(2 * i + 2, m, r, lq);
for (int j = 0; j < tmp; j++) {
dp[i][j] = merge(dp[2 * i + 1][j], dp[2 * i + 2][j]);
}
}
}
void get(int i, int l, int r, int lq, int rq) {
if (lq >= r || l >= rq) return;
if (lq <= l && r <= rq) {
for (int j = 0; j < tmp; j++) f[j] = merge(f[j], dp[i][j]);
return;
}
int m = (r + l) / 2;
get(2 * i + 1, l, m, lq, rq);
get(2 * i + 2, m, r, lq, rq);
}
void calc(int v) {
ok[v] = 0;
good[v] = 0;
if (f[v].first != -1) ok[v] = 1, good[v] = 1;
for (auto u : G[v]) {
calc(u.to);
ok[v] |= ok[u.to];
}
}
void get(int v, int s) {
for (auto u : G[v]) {
s += ok[u.to];
}
s += good[v];
for (auto u : G[v]) {
if (s - ok[u.to] > 0) {
f[u.to].first = u.node;
if (f[u.to].second == -1) f[u.to].second = u.node;
get(u.to, 1);
} else {
get(u.to, 0);
}
if (ok[u.to]) {
if (f[v].second == -1 || h[f[v].second] < h[u.node]) f[v].second = u.node;
if (f[v].first == -1 || h[f[v].first] > h[u.node]) f[v].first = u.node;
if (f[v].first != -1 && f[v].second == -1) f[v].second = f[v].first;
if (f[v].second != -1 && f[v].first == -1) f[v].first = f[v].second;
}
}
}
int check(int v, int p, int l, int r) {
int ans = (l <= v && v <= r && s[v] == '1');
for (auto [u, w] : g[v]) {
if (u != p) ans |= check(u, v, l, r);
}
return ans;
}
main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#endif // HOME
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q, u, v, w, l, r, type;
cin >> n >> q;
cin >> s;
s = "#" + s;
vector < vector < int > > edge;
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
assert(w >= 0);
edge.push_back({u, v, w});
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0, 0);
assert(tmp < K);
build(0, 1, n + 1);
for (int i = 1; i <= q; i++) {
cin >> type;
if (type == 2) {
cin >> l >> r;
for (int j = 0; j < tmp; j++) f[j] = {-1, -1};
get(0, 1, n + 1, l, r + 1);
/*for (int j = 0; j < tmp; j++) {
cout << f[j].first << " " << f[j].second << endl;
}*/
set < pair < int, int > > used;
ans = 0;
calc(0);
get(0, 0);
int flag = 0;
for (int j = 0; j < tmp; j++) {
if (f[j].first == -1) f[j].first = f[j].second;
else if (f[j].second == -1) f[j].second = f[j].first;
//cout << f[j].first << " " << f[j].second << endl;
if (f[j].first != -1) {
ans += h[f[j].second] - h[f[j].first], flag = 1;
u = f[j].second, v = f[j].first;
while (u != v) {
assert(used.find({u, lst[u]}) == used.end());
used.insert({u, lst[u]});
}
}
}
ll out;
if (flag) out = 2 * ans;
else out = -1;
cout << out << '\n';
ll res = -1;
for (int j = l; j <= r; j++) {
if (s[j] == '1') res = 0;
}
if (res == 0) {
for (auto key : edge) {
assert(key[2] >= 0);
if (check(key[0], key[1], l, r) && check(key[1], key[0], l, r)) res += key[2];
}
res *= 2;
}
//assert(out == res);
} else {
cin >> u;
update(0, 1, n + 1, u);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
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