QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#646235 | #6404. Shuttle Tour | crimsonsunset# | WA | 57ms | 3872kb | C++20 | 6.9kb | 2024-10-16 21:50:38 | 2024-10-16 21:50:38 |
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 = 1e9;
};
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 = 1e9;
}
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)1e9};
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)1e9};
return get(0, 0, sz, ql, qr);
}
};
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);
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;
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});
}
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]);
}
}
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;
for (int i = 0; i < lolkek.size(); ++i) {
// cout << "FUCK" << endl;
Node tt = xx[i].get(l, r + 1);
if (tt.mn == (int)1e9) continue;
// 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;
}
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 (auto e : xx) {
// cout << e << endl;
ans += D(curr, e);
curr = e;
}
cout << ans << "\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: 3872kb
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: 57ms
memory: 3764kb
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:
2788264120 -1 0 7086170248 2788264120 0 0 0 0 0 4297906128 -1 0 -1 -1 0 0 -1 -1 0 4297906128 -1 -1 -1 2716712308 2716712308 -1 -1 4297906128 -1 0 6281392916 -1 -1 -1 -1 1300013146 5774653100 -1 -1 -1 -1 0 -1 0 4297906128 -1 -1 3791166312 1300013146 1300013146 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
wrong answer 1st numbers differ - expected: '17149847378', found: '2788264120'