QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#421456 | #7103. Red Black Tree | ucup-team3215# | AC ✓ | 1978ms | 30764kb | C++20 | 4.5kb | 2024-05-25 19:12:25 | 2024-05-25 19:12:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> pred, cnt;
DSU(int n) : pred(n), cnt(n, 1) {
iota(pred.begin(), pred.end(), 0);
}
int find(int x) { return (x == pred[x] ? x : pred[x] = find(pred[x])); }
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y)return;
if (cnt[x] > cnt[y])swap(x, y);
pred[x] = y;
cnt[y] += cnt[x];
}
};
#define all(x) (x).begin(), (x).end()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pll = array<ll, 2>;
struct edge {
int u, v;
ll w;
};
const int A = 18;
using ar = array<int, A>;
ar emptyar = {};
const ll INF = 1e18;
using graph = vector<vector<edge>>;
vi tin, tout, is_red;
vl dist;
int timer;
vector<ar> up;
bool is_anc(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v) {
if (is_anc(u, v)) {
return u;
}
if (is_anc(v, u)) {
return v;
}
for (int j = A - 1; j--;) {
if (!is_anc(up[u][j], v)) {
u = up[u][j];
}
}
return up[u][0];
}
void dfs(int u, int p, const graph & g, DSU & d) {
tin[u] = ++timer;
for (auto [_, v, w] : g[u]) {
if (v == p) {
continue;
}
up[v][0] = u;
if (!is_red[v]) {
dist[v] = w + dist[u];
d.unite(u, v);
}
dfs(v, u, g, d);
}
tout[u] = ++timer;
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
is_red.assign(n, 0);
for (int i = 0; i < m; ++i) {
int r;
cin >> r;
is_red[--r] = 1;
}
graph g(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
--u, --v;
g[u].push_back({u,v,w});
g[v].push_back({v,u,w});
}
tin.assign(n, 0), tout.assign(n, 0);
up.assign(n, emptyar);
dist.assign(n, 0);
timer = 0;
DSU d(n);
dfs(0, -1, g, d);
for (int j = 0; j + 1 < A; ++j) {
for (int i = 0; i < n; ++i) {
up[i][j + 1] = up[up[i][j]][j];
}
}
while (q--) {
int k;
cin >> k;
map<int, int> toid;
vector<vector<pll> > comps;
for (int i = 0; i < k; ++i) {
int v;
cin >> v;
--v;
int lv = d.find(v), id = -1;
if (!toid.count(lv)) {
id = comps.size();
comps.emplace_back();
toid[lv] = id;
} else {
id = toid[lv];
}
comps[id].push_back({dist[v], v});
}
int ncomps = comps.size();
vector<vi> clca(ncomps);
for (int i = 0; i < ncomps; ++i) {
sort(all(comps[i]), greater<pll>());
int cc = comps[i].size();
clca[i].resize(cc);
clca[i][0] = comps[i][0][1];
for (int j = 1; j < cc; ++j) {
clca[i][j] = lca(clca[i][j - 1], comps[i][j][1]);
}
}
ll lo = -1, hi = INF;
while (lo + 1 < hi) {
ll mid = (lo + hi) / 2;
vi last(ncomps, -1);
int id = -1;
bool good = true;
for (int i = 0; i < ncomps; ++i) {
int cc = comps[i].size();
for (int j = 0; j < cc; ++j) {
if (dist[comps[i][j][1]] > mid) {
last[i] = j;
}
}
if (id == -1 && last[i] != -1) {
id = i;
}
if (last[i] != -1 && i != id) {
good = false;
}
}
if (id == -1) {
hi = mid;
continue;
}
if (!good) {
lo = mid;
continue;
}
int l = clca[id][last[id]];
for (int j = 0; j <= last[id]; ++j) {
if (dist[comps[id][j][1]] - dist[l] > mid) {
good = false;
}
}
if (good) {
hi = mid;
} else {
lo = mid;
}
}
cout << hi << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
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: 1978ms
memory: 30764kb
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