QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199297 | #6404. Shuttle Tour | UrgantTeam | WA | 1881ms | 11980kb | C++23 | 6.1kb | 2023-10-04 04:48:14 | 2023-10-04 04:48:14 |
Judging History
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);
set < int > goal;
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);
int flag = 0;
for (int j = 0; j < tmp; j++) {
if (f[j].first != -1) flag = 1;
}
if (!flag) {
cout << -1 << '\n';
continue;
}
/*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);
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]});
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];
used.erase({key[0], key[1]});
used.erase({key[1], key[0]});
}
}
res *= 2;
}
assert(used.size() == 0);
//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: 100
Accepted
time: 2ms
memory: 11788kb
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: 1881ms
memory: 11980kb
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 13395458744 11814264924 11521665648 11814264924 4793160250 18332625722 8737390194 10363026314 11819008744 3213506564 9250086946 11167895448 7136547688 2726031940 13087469738 0 -1 7245018196 10017477006 10117168752 10017477006 13598441870 5923626370 4954957854 12913949226 0 13640042476...
result:
wrong answer 3rd numbers differ - expected: '26540740138', found: '13395458744'