QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#456884 | #7103. Red Black Tree | ucup-team3282 | WA | 1425ms | 119908kb | C++14 | 3.1kb | 2024-06-28 16:21:54 | 2024-06-28 16:21:57 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 2e5+9;
int fa[N][21], dep[N], dis[N], n, m, q, r[N], isred[N], anc[N], nr = 1, node[N], k, tot, dfn[N], LG[N], st[N][21], rev[N][21], pos[N], cnt, T;
vector<pair<int, int>> adj[N];
void dfs1(int u, int f, int d) {
fa[u][0] = f; dfn[++tot] = u; dep[tot] = d; pos[u] = tot;
if (!isred[u]) anc[u] = nr;
int tmp = nr;
for (auto i : adj[u]) {
if (i.fi == f) continue;
if (isred[i.fi]) nr = i.fi;
dis[i.fi] = dis[u] + i.se;
dfs1(i.fi, u, d + 1);
dfn[++tot] = u; dep[tot] = d;
}
nr = tmp;
}
void init() {
for (int i = 2; i <= tot; i++) LG[i] = LG[i >> 1] + 1;
for (int i = 1; i <= tot; i++) {
st[i][0] = dep[i];
rev[i][0] = dfn[i];
}
for (int j = 1; j <= LG[tot]; j++) {
for (int i = 1; i + (1 << j) - 1 <= tot; i++) {
if (st[i][j - 1] < st[i + (1 << (j - 1))][j - 1]) st[i][j] = st[i][j - 1], rev[i][j] = rev[i][j - 1];
else st[i][j] = st[i + (1 << (j - 1))][j - 1], rev[i][j] = rev[i + (1 << (j - 1))][j - 1];
}
}
}
int query(int l, int r) {
int k = LG[r - l + 1];
return st[l][k] < st[r - (1 << k) + 1][k] ? rev[l][k] : rev[r - (1 << k) + 1][k];
}
int lca(int x, int y) {
if (pos[x] > pos[y]) swap(x, y);
return query(pos[x], pos[y]);
}
bool check(int lim) {
int cc = 0;
for (int i = 1; i <= k; i++) {
int u = node[i];
if (dis[u] - dis[anc[u]] <= lim) continue;
cc++;
}
if (cc == 0) return true;
int zx = 0;
for (int i = 1; i <= k; i++) {
int u = node[i];
if (dis[u] - dis[anc[u]] > lim) {
if (!zx) {
zx = u;
continue;
}
zx = lca(zx, u);
}
}
int mx = -1;
for (int i = 1; i <= k; i++) {
int u = node[i];
if (dis[u] - dis[anc[u]] > lim) {
mx = max(mx, dis[u]);
}
}
return mx - dis[zx] <= lim;
}
void solve() {
cin >> n >> m >> q;
memset(dis, 0, sizeof(int) * (2 * n + 9));
memset(isred, 0, sizeof(int) * (2 * n + 9));
memset(dep, 0, sizeof(int) * (2 * n + 9));
memset(anc, 0, sizeof(int) * (2 * n + 9));
memset(pos, 0, sizeof(int) * (2 * n + 9));
memset(dfn, 0, sizeof(int) * (2 * n + 9));
nr = 1;
for (int i = 0; i <= n; i++) adj[i].clear();
for (int i = 1; i <= m; i++) {
cin >> r[i];
isred[r[i]] = true;
anc[r[i]] = r[i];
}
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
tot = 0;
dfs1(1, 0, 1);
init();
while (q--) {
cnt++;
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> node[i];
}
int l = 0, r = 1e9, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (cnt == 18) cout << mid << endl;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
if (cnt == 18 || T != 522) cout << ans << "\n";
}
}
signed main() {
//freopen("B.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
for (int i = 1; i <= T; i++) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 25816kb
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: -100
Wrong Answer
time: 1425ms
memory: 119908kb
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:
500000000 750000000 625000000 687500000 718750000 703125000 695312500 691406250 693359375 692382812 691894531 691650390 691528320 691467285 691436767 691421508 691413879 691417693 691419600 691420554 691421031 691421269 691421388 691421448 691421478 691421463 691421470 691421474 691421476 691421475 ...
result:
wrong answer 1st lines differ - expected: '148616264', found: '500000000'