QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#158994 | #7103. Red Black Tree | ucup-team228# | AC ✓ | 836ms | 36380kb | C++20 | 5.2kb | 2023-09-02 17:18:33 | 2023-09-02 17:18:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
* TOUR SIZE IS TWO TIMES MORE THAN N, SO UPDATE SPARSE_TABLE::N CORRESPONDINGLY
*
* checked on this problem: https://codeforces.com/problemset/problem/342/E
*/
enum TableType { VAL, ARG };
template <typename T, TableType S = TableType::VAL, typename Cmp = less<T>>
struct sparse_table{
// VAL returns value, ARG returns position of value
// less<> for minimum, greater<> for maximum
// d[i][j] = min(a[i], a[i + 1], ... , a[i + (1 << j) - 1])
// get(l, r) = min(a[l], a[l + 1], ... , a[r])
static const int N = 2e5 + 10;
static const int L = 19;
T a[N];
int d[N][L], rem[N];
void build(int n, Cmp cmp = {}) {
for (int i = 1; i <= n; i++) { d[i][0] = i; }
for (int j = 1; j <= L - 1; j++) {
for (int i = 1; i <= n; i++) {
if (i + (1 << j) - 1 > n) { continue; }
d[i][j] = cmp(a[d[i][j - 1]], a[d[i + (1 << (j - 1))][j - 1]]) ? d[i][j - 1] : d[i + (1 << (j - 1))][j - 1];
}
}
for (int i = 1; i <= n; i++) { rem[i] = log2(i); }
}
T get(int l, int r, Cmp cmp = {}) {
int lg = rem[r - l + 1];
int pos = cmp(a[d[l][lg]], a[d[r - (1 << lg) + 1][lg]]) ? d[l][lg] : d[r - (1 << lg) + 1][lg];
if constexpr (S == TableType::VAL) { return a[pos]; } else { return pos; }
}
};
sparse_table<int, TableType::ARG> table;
const ll inf = 1e18;
const int N = 1e5 + 10;
int depth[N], in[N], out[N];
vector<pair<int, int>> g[N];
vector<int> tour;
bool is_red[N];
int up[N];
ll mem[N];
void init(int n) {
for (int i = 1; i <= n; i++) {
depth[i] = 0;
in[i] = 0;
out[i] = 0;
g[i].clear();
is_red[i] = false;
up[i] = 0;
mem[i] = 0;
}
tour.clear();
}
void dfs_lca(int v = 1, int p = 1) {
in[v] = tour.size();
tour.push_back(v);
for (auto [to, w] : g[v]) {
if (to != p) {
depth[to] = depth[v] + 1;
dfs_lca(to, v);
tour.push_back(v);
}
}
out[v] = tour.size() - 1;
}
int lca(int u, int v) {
if (out[u] > out[v]) {
swap(u, v);
}
return tour[table.get(in[u] + 1, out[v] + 1) - 1];
}
void precalc_lca() {
dfs_lca();
for (int i = 1; i <= tour.size(); i++) {
table.a[i] = depth[tour[i - 1]];
}
table.build(tour.size());
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
void dfs_up(int v = 1, int p = 1) {
if (is_red[v]) {
up[v] = v;
mem[v] = 0;
}
for (auto [to, w] : g[v]) {
if (to != p) {
up[to] = up[v];
mem[to] = mem[v] + w;
dfs_up(to, v);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int t;
cin >> t;
while (t--) {
int n, m, q;
cin >> n >> m >> q;
init(n);
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
is_red[x] = true;
}
for (int i = 1; i <= n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
precalc_lca();
dfs_up();
while (q--) {
int k;
cin >> k;
vector<int> a(k);
for (int& v : a) {
cin >> v;
}
vector<pair<ll, int>> b;
b.reserve(k);
for (int v : a) {
b.emplace_back(mem[v], v);
}
sort(b.begin(), b.end());
if (b.back().first == 0) {
cout << "0\n";
} else {
int x = b.back().second;
vector<tuple<int, int, ll>> c;
c.reserve(k);
ll other = 0;
for (int v : a) {
int l = lca(x, v);
if (depth[l] <= depth[up[x]] || depth[l] <= depth[up[v]]) {
other = max(other, mem[v]);
} else {
c.emplace_back(depth[l], l, mem[v]);
}
}
sort(c.begin(), c.end());
vector<ll> pref(c.size());
pref[0] = get<2>(c.front());
for (int i = 1; i < c.size(); i++) {
pref[i] = max(pref[i - 1], get<2>(c[i]));
}
vector<ll> suf(c.size());
suf[c.size() - 1] = get<2>(c.back());
for (int i = int(c.size()) - 2; i >= 0; i--) {
suf[i] = max(suf[i + 1], get<2>(c[i]));
}
ll ans = inf;
for (int i = 0; i < c.size(); i++) {
ans = min(ans, max({other, i == 0 ? 0 : pref[i - 1], suf[i] - mem[get<1>(c[i])]}));
}
cout << ans << "\n";
}
}
}
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11920kb
input:
2 12 2 4 1 9 1 2 1 2 3 4 3 4 3 3 5 2 2 6 2 6 7 1 6 8 2 2 9 5 9 10 2 9 11 3 1 12 10 3 3 7 8 4 4 5 7 8 4 7 8 10 11 3 4 5 12 3 2 3 1 2 1 2 1 1 3 1 1 1 2 1 2 3 1 2 3
output:
4 5 3 8 0 0 0
result:
ok 7 lines
Test #2:
score: 0
Accepted
time: 836ms
memory: 36380kb
input:
522 26 1 3 1 1 4 276455 18 6 49344056 18 25 58172365 19 9 12014251 2 1 15079181 17 1 50011746 8 9 2413085 23 24 23767115 22 2 26151339 26 21 50183935 17 14 16892041 9 26 53389093 1 20 62299200 24 18 56114328 11 2 50160143 6 26 14430542 16 7 32574577 3 16 59227555 3 15 8795685 4 12 5801074 5 20 57457...
output:
148616264 148616264 0 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 0 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164 181713164 181...
result:
ok 577632 lines
Extra Test:
score: 0
Extra Test Passed