QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199280 | #6404. Shuttle Tour | UrgantTeam | WA | 108ms | 11840kb | C++23 | 4.1kb | 2023-10-04 03:19:42 | 2023-10-04 03:19:42 |
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 = 50;
string s;
int numb[maxn], tmp = 1;
ll h[maxn], ans;
vector < pair < int, int > > g[maxn];
pair < int, int > dp[(1 << 19)][K];
pair < int, int > f[K];
vector < pt > G[K];
int ok[maxn];
void dfs(int v, int p, int cur) {
assert(cur < K);
int flag = 1;
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});
dfs(u, v, tmp++);
}
}
}
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) {
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;
if (f[v].first != -1) ok[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 += ok[v];
for (auto u : G[v]) {
if (s - ok[u.to] > 0) {
f[u.to].first = 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;
}
}
}
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;
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0, 0);
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);
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;
}
if (flag) cout << 2 * ans << '\n';
else cout << -1 << '\n';
} 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: 1ms
memory: 9836kb
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: 108ms
memory: 11840kb
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 11814264924 11521665648 11814264924 6776647038 13608712818 10720876982 12346513102 13802495532 6497006498 8679759592 13151382236 9120034476 2726031940 13517229452 3863969614 -1 9228504984 12000963794 12100655540 12000963794 15581928658 7907113158 6938444642 12414084300 514...
result:
wrong answer 4th numbers differ - expected: '29613692754', found: '11814264924'