QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#655402 | #6404. Shuttle Tour | crimsonsunset | Compile Error | / | / | C++20 | 5.6kb | 2024-10-19 04:11:31 | 2024-10-19 04:11:32 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops,inline,fastmath")
#pragma GCC target("avx,avx2,fma,bmi2,abm,popcnt,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
pair<int, int> tr[(int) 4e5];
struct seg_tree {
int n;
seg_tree() = default;
seg_tree(int n) : n(n) {
fill(tr, tr + 2 * n, make_pair(1e9 + 1, -1));
}
void upd(int k, pair<int, int> x) {
for (tr[k += n] = x; k > 1; k >>= 1, tr[k] = min(tr[k << 1], tr[k << 1 | 1]));
}
int get(int l, int r) {
pair<int, int> ans ={1e9 + 1, -1};
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) ans = min(tr[l++], ans);
if (~r & 1) ans = min(tr[r--], ans);
}
return ans.ss;
}
void upd(int v, int val) {
if (val != -1)
upd(v, {val, v});
else
upd(v, {1e9 + 1, -1});
}
};
pair<int, int> d[22][(int) 4e5];
struct sparse_table {
sparse_table() {}
void build(vector<pair<int, int>> a) {
int n = a.size();
for (int i = 0; i < n; ++i)
d[0][i] = a[i];
for (int i = 1; i <= __lg(n); ++i)
for (int j = 0; j + (1 << (i - 1)) < n; ++j)
d[i][j] = min(d[i - 1][j], d[i - 1][j + (1 << (i - 1))]);
}
int get(int l, int r) {
if (l > r)
swap(l, r);
++r;
int t = __lg(r - l);
return min(d[t][l], d[t][r - (1 << t)]).ss;
}
} sp;
vector<pair<int, int>> gr[(int) 2e5];
vector<int> cmp[(int) 2e5], need[(int) 2e5];
array<int, 3> que[(int) 2e5];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
string s;
cin >> s;
for (int i = 1, u, v, c; i < n; ++i) {
cin >> u >> v >> c;
--u, --v;
gr[u].push_back({v, c});
gr[v].push_back({u, c});
}
for (int i = 0; i < q; ++i) {
cin >> que[i][0];
if (que[i][0] == 1)
cin >> que[i][1], --que[i][1];
else
cin >> que[i][1] >> que[i][2], --que[i][1], --que[i][2];
}
vector<int> tin(n), depth(n), pos(n);
vector<ll> dist(n);
int timer = 0;
vector<pair<int, int>> ord;
auto dfs = [&](auto self, int v, int p, ll d, int dp) -> void {
tin[v] = timer++;
pos[v] = ord.size();
dist[v] = d;
depth[v] = dp;
ord.push_back({depth[v], v});
for (auto [u, c]: gr[v])
if (u != p) {
self(self, u, v, d + c, dp + 1);
ord.push_back({depth[v], v});
}
};
dfs(dfs, 0, -1, 0, 0);
sp.build(ord);
auto dfs2 = [&](auto self, int v, int p) -> void {
tin[v] = timer++;
for (auto [u, c]: gr[v])
if (u != p)
self(self, u, v);
};
string t = s;
for (int i = 0; i < n; ++i)
if (gr[i].size() <= 1) {
s = t;
timer = 0;
dfs2(dfs2, i, -1);
seg_tree tr(n);
for (int j = 0; j < n; ++j)
if (s[j] == '1')
tr.upd(j, tin[j]);
for (int j = 0; j < q; ++j) {
if (que[j][0] == 1) {
if (s[que[j][1]] == '1') {
tr.upd(que[j][1], -1);
s[que[j][1]] = '0';
} else {
tr.upd(que[j][1], tin[que[j][1]]);
s[que[j][1]] = '1';
}
} else {
auto x = tr.get(que[j][1], que[j][2]);
need[j].push_back(x);
}
}
}
timer = 0;
dfs2(dfs2, 0, -1);
for (int i = 0; i < q; ++i) {
if (need[i].size()) {
sort(all(need[i]));
need[i].resize(unique(all(need[i])) - need[i].begin());
if (need[i][0] == -1) {
cout << -1 << '\n';
continue;
}
vector<pair<int, int>> v;
for (int j = 0; j < need[i].size(); ++j)
v.push_back({tin[need[i][j]], need[i][j]});
sort(all(v));
int root = v[0].ss;
for (int j = 1; j < v.size(); ++j)
root = sp.get(pos[root], pos[v[j].ss]);
vector<int> st = {root}, vr = {root};
for (int j = 0; j < v.size(); ++j) {
int last = -1;
if (v[j].ss == st.back())
continue;
int an = sp.get(pos[st.back()], pos[v[j].ss]);
while (!st.empty() && depth[st.back()] > depth[an]) {
last = st.back();
st.pop_back();
}
if (an == st.back()) {
cmp[st.back()].push_back(v[j].ss);
} else {
cmp[st.back()].pop_back();
cmp[st.back()].push_back(an);
cmp[an].push_back(last);
cmp[an].push_back(v[j].ss);
st.push_back(an);
vr.push_back(an);
}
st.push_back(v[j].ss);
vr.push_back(v[j].ss);
}
ll ans = 0;
for (int j: vr)
for (int u: cmp[j])
ans += dist[u] - dist[j];
for (int j: vr)
cmp[j].clear();
cout << ans * 2 << '\n';
}
}
}
详细
answer.code:1:55: warning: bad option ‘-ffastmath’ to pragma ‘optimize’ [-Wpragmas] 1 | #pragma GCC optimize("O3,unroll-loops,inline,fastmath") | ^ answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] 2 | #pragma GCC target("avx,avx2,fma,bmi2,abm,popcnt,tune=native") | ^ answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to attribute ‘optimize’ [-Wattributes] answer.code:2:62: warning: bad option ‘-ffastmath’ to at...