QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#646344 | #6404. Shuttle Tour | crimsonsunset# | WA | 178ms | 3864kb | C++20 | 9.1kb | 2024-10-16 22:19:19 | 2024-10-16 22:19:19 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long long ll;
typedef long double ld;
struct Node {
int mx = 0, mn = 1e16;
};
struct SegmentTree {
vector<int> lol;
vector<Node> tr;
int sz;
SegmentTree() {};
void build(vector<int> lollol) {
lol = lollol;
sort(all(lol));
lol.push_back(3e5);
int n = lol.size();
sz = (1ll<<(int)(log2(n)))*2;
tr.resize(2*sz);
};
Node merge(Node a, Node b) {
Node c = {max(a.mx, b.mx), min(a.mn, b.mn)};
return c;
}
void update(int v, int l, int r, int ind, int x) {
if(l > ind || r <= ind) return;
if(r - l == 1) {
tr[v].mn = x;
tr[v].mx = x;
if (x == -1) {
tr[v].mx = 0;
tr[v].mn = 1e16;
}
return;
}
int m = (l + r) / 2;
update(2 * v + 1, l, m, ind, x);
update(2 * v + 2, m, r, ind, x);
tr[v] = merge(tr[2 * v + 1], tr[2 * v + 2]);
// cout << "mnmx" << tr[v].mn << ' ' << tr[v].mx << '\n';
};
void update(int ind, int x) {
ind = (lower_bound(all(lol), ind) - lol.begin());
// cout << "XXX" << ind << '\n';
update(0, 0, sz, ind, x);
};
Node get(int v, int l, int r, int ql, int qr) {
if(ql <= l && qr >= r) {
return tr[v];
}
if(l >= qr || r <= ql) return {0, (int)1e16};
int m = (l + r) / 2;
return merge(get(2 * v + 1, l, m, ql, qr), get(2 * v + 2, m, r, ql, qr));
};
Node get(int ql, int qr) {
// return tr[0];
// cout << ql << ' ' << qr << endl;
// for (auto e : lol) cout << e << ' '; cout << endl;
ql = lower_bound(all(lol), ql) - lol.begin();
qr = lower_bound(all(lol), qr) - lol.begin();
// cout << ql << ' ' << qr << endl;
if (ql == qr) return {0, (int)1e16};
return get(0, 0, sz, ql, qr);
}
};
vector<int> fuckfuck;
vector<vector<pair<int, int>>> gr;
vector<int> lol;
map<int, vector<int>> backlol;
vector<map<int, int>> lol2;
vector<int> h, pr, tin, tout;
int timer = 1;
void dfs(int v, int p) {
tin[v] = timer; timer++;
pr[v] = p;
for (auto e : gr[v]) {
if (e.first == p) continue;
h[e.first] = h[v] + e.second;
dfs(e.first, v);
fuckfuck[lol[e.first]] += e.second;
lol[v] = lol[e.first];
}
if (gr[v].size() == 1 && pr[v] != -1) lol[v] = v;
backlol[lol[v]].push_back(v);
tout[v] = timer; timer++;
lol2[lol[v]][h[v]] = v;
}
map<pair<int, int>, int> d;
vector<int> lolkek;
int D(int i, int j) {
if (i == j) return 0;
if (h[i] > h[j]) swap(i, j);
if (tin[i] < tin[j] && tout[i] > tout[j]) return h[j] - h[i];
return h[i] + h[j] - 2 * d[{lolkek[lol[i]], lolkek[lol[j]]}];
}
void solve() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
int sum = 0;
fuckfuck.resize(n);
gr.resize(n); lol.resize(n); h.resize(n); pr.resize(n); tin.resize(n); tout.resize(n); lol2.resize(n);
for (int i = 0; i < n - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u; --v;
gr[u].push_back({v, w});
gr[v].push_back({u, w});
sum += 2 * w;
}
if (n == 1) {
for (int j = 0; j < q; ++j) {
int t;
cin >> t;
if (t == 1) {
int ind;
cin >> ind; --ind;
if (s[ind] == '0') {
s[ind] = '1';
}
else {
s[ind] = '0';
}
}
else {
int l, r;
cin >> l >> r; --l; --r;
if (s[l] == '0') cout << "-1\n";
else cout << "0\n";
}
}
return;
}
dfs(0, -1);
for (int i = 1; i < n; ++i) {
if (gr[i].size() == 1) lolkek.push_back(i);
}
for (auto i : lolkek) {
for (auto j : lolkek) {
int xi = i, xj = j;
while (xi != xj) {
if (h[xi] >= h[xj]) xi = pr[xi];
else xj = pr[xj];
}
d[{i, j}] = h[xi];
}
}
// for (auto e : lol) cout << e << '\n';
map<int, int> lol5;
for (int i = 0; i < lolkek.size(); ++i) lol5[lolkek[i]] = i;
for (int i = 0; i < n; ++i) lol[i] = lol5[lol[i]];
vector<SegmentTree> xx(lolkek.size());
for (int i = 0; i < lolkek.size(); ++i) {
// for (auto e : backlol[lolkek[i]]) cout << e << ' '; cout << endl;
xx[i].build(backlol[lolkek[i]]);
}
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
xx[lol[i]].update(i, h[i]);
}
}
int log2n = 20;
pr[0] = 0;
vector<vector<int>> binups(log2n, vector<int>(n));
for (int i = 0; i < n; ++i) binups[0][i] = pr[i];
for (int i = 1; i < log2n; ++i) {
for (int j = 0; j < n; ++j) {
binups[i][j] = binups[i - 1][binups[i - 1][j]];
}
}
for (int i = 0; i < q; ++i) {
int t;
cin >> t;
if (t == 1) {
int ind;
cin >> ind; --ind;
if (s[ind] == '0') {
s[ind] = '1';
xx[lol[ind]].update(ind, h[ind]);
}
else {
s[ind] = '0';
xx[lol[ind]].update(ind, -1);
}
}
else {
int l, r;
cin >> l >> r; --l; --r;
set<int> cur;
int ans = 0;
int uppest = -1;
int ct = 0;
for (int i = 0; i < lolkek.size(); ++i) {
// cout << "FUCK" << endl;
Node tt = xx[i].get(l, r + 1);
if (tt.mn == (int)1e16) {
// ans += 2 * fuckfuck[lolkek[i]];
continue;
}
// if (uppest == -1) {
// uppest = lol2[lolkek[i]][tt.mn];
// }
// else {
// int v = lol2[lolkek[i]][tt.mn];
// if (tin[uppest] < tin[v] && tout[uppest] > tout[v]) {}
// else if (tin[uppest] > tin[v] && tout[uppest] < tout[v]) {
// uppest = v;
// }
// else {
// for (int i = 19; i >= 0; --i) {
// if (tin[binups[i][uppest]] < tin[v] && tout[binups[i][uppest]] > tout[v]) continue;
// uppest = binups[i][uppest];
// }
// uppest = pr[uppest];
// }
// }
// ct++;
// cur.insert(lol2[lolkek[i]][tt.mx]);
// ans += 2 * tt.mx;
// cout << lol2[lolkek[i]][tt.mn] << ' ' << lol2[lolkek[i]][tt.mx] << endl;
cur.insert(lol2[lolkek[i]][tt.mn]);
cur.insert(lol2[lolkek[i]][tt.mx]);
}
if (cur.size() == 0) {
cout << "-1\n";
continue;
}
// if (uppest == -1) {
// cout << "-1\n";
// continue;
// }
// for (auto e : cur) {
// bool ok = 1;
// for (auto i : cur) {
// if (tin[e] < tin[i] && tout[e] > tout[i]) ok = 0;
// }
// // if (ok) cout << "X" << e << endl;
// if (ok) ans += 2 * (h[lolkek[lol[e]]] - h[e]);
// }
// cout << sum - 2 * uppest - ans << '\n';
vector<int> xx;
for (auto e : cur) xx.push_back(e);
sort(all(xx), [&](int i, int j) {
return tin[i] < tin[j];
});
// int curr = xx[xx.size() - 1];
for (int i = 1; i < xx.size(); ++i) {
int e = xx[i];
int curr = xx[0];
for (int j = 1; j < i; ++j) {
if (tout[xx[j]] > tout[curr]) curr = xx[j];
}
// cout << e << endl;
ans += D(curr, e);
curr = e;
}
cout << ans * 2 << "\n";
}
}
}
signed main() {
int tc = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#endif
// cin >> tc;
for (int t = 1; t <= tc; t++) {
// cout << "Case #" << t << ": ";
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
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: 178ms
memory: 3864kb
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:
35590234108 -1 40876145386 68742197646 42544048828 40303834958 25909885716 39267482644 52349655026 41299090016 74669460754 13469153044 9380710234 38932248752 26477596836 2856655228 22978874106 0 -1 10440149760 51854927648 32276479402 36453251880 25951598516 15346314934 11712556166 27715407096 0 5673...
result:
wrong answer 1st numbers differ - expected: '17149847378', found: '35590234108'