QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#160053 | #7103. Red Black Tree | ucup-team1453# | AC ✓ | 874ms | 96660kb | C++14 | 3.8kb | 2023-09-02 19:20:59 | 2023-09-02 19:20:59 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define sz(a) ((int) a.size())
#define vi vector<int>
#define ll long long
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
using namespace std;
const int N = 4e5 + 7;
template < int N > struct stlca {
int n;
int ehd[N], ev[N * 2], enx[N * 2], ew[N * 2], eid;
void Eadd(int u, int v, int w) {
enx[++eid] = ehd[u], ev[eid] = v, ew[eid] = w, ehd[u] = eid;
}
void add(int u, int v, int w) {
Eadd(u, v, w);
Eadd(v, u, w);
}
int q[N], s[N], fa[N], lg[N], top;
ll dep[N];
int cs[20][N], up[20][N];
void dfs1(int x) {
++top, cs[0][q[x] = top] = fa[x];
up[0][x] = fa[x];
L(i, 1, 19) {
up[i][x] = up[i - 1][up[i - 1][x]];
}
for(int i = ehd[x]; i; i = enx[i]) if(ev[i] != fa[x])
dep[ev[i]] = dep[x] + ew[i], fa[ev[i]] = x, dfs1(ev[i]);
}
inline int cmin(int &x, int &y) {
return dep[x] < dep[y] ? x : y;
}
int lca(int l, int r) {
if(l == r) return l;
l = q[l], r = q[r];
if(l > r) swap(l, r);
++l;
int p = lg[r - l + 1];
return cmin(cs[p][l], cs[p][r - (1 << p) + 1]);
}
inline ll dis(int x, int y) {
return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
void mk(int xn) {
n = xn, dfs1(1);
L(i, 2, top) lg[i] = lg[i >> 1] + 1;
L(i, 1, 19) L(j, 1, top - (1 << i) + 1)
cs[i][j] = cmin(cs[i - 1][j], cs[i - 1][j + (1 << (i - 1))]);
}
void clear() {
L(i, 1, n) ehd[i] = 0, fa[i] = 0;
top = 0, n = 0, eid = 0;
}
} ;
stlca < N > st;
struct node {
int x, y;
ll dis;
node() {
x = y = 0;
dis = 0;
}
void insert(int p) {
if(!x) return x = p, void();
if(!y) return y = p, dis = st.dis(x, y), void();
ll u = st.dis(x, p), v = st.dis(y, p);
if(max(u, v) <= dis) return ;
if(u > v) {
y = p;
} else {
x = p;
}
dis = max(u, v);
}
};
int n, m, q;
vector < pair < int, int > > e[N];
ll dis[N];
int pos[N], top;
int up[20][N];
inline ll jump(int x, int y) {
if(!x || !y) return 0;
int lca = st.lca(x, y);
ll dx = st.dep[x] - st.dep[lca];
ll dy = st.dep[y] - st.dep[lca];
if(dx < dy) swap(dx, dy), swap(x, y);
ll sum = (dx + dy) / 2;
int z = x;
R(t, 19, 0) {
int go = st.up[t][z];
if(go && st.dep[x] - st.dep[go] <= sum)
z = go;
}
ll ans1 = max(st.dis(x, z), st.dis(y, z));
z = st.fa[z];
ll ans2 = z ? max(st.dis(x, z), st.dis(y, z)) : (ll)1e18;
// cout << x << ' ' << y << " : " << z << ' ' <<
// min(ans1, ans2) << ' ' << st.dis(x, y) << '\n';
return min(ans1, ans2);
}
void DFS(int x) {
for(auto E : e[x]) {
int v = E.first;
int w = E.second;
if(v != st.fa[x]) {
if(dis[v] > dis[x] + w) dis[v] = dis[x] + w;
DFS(v);
}
}
}
void Main() {
cin >> n >> m >> q;
L(i, 1, n) dis[i] = 1e18;
priority_queue < pair < ll, int > > q;
L(i, 1, m) {
int x;
cin >> x;
dis[x] = 0;
q.push({0, x});
}
L(i, 1, n - 1) {
int u, v, w;
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
st.add(u, v, w);
}
st.mk(n);
DFS(1);
while(::q--) {
cin >> top;
L(i, 1, top) {
cin >> pos[i];
}
sort(pos + 1, pos + top + 1, [&] (int x, int y) {
return dis[x] > dis[y];
});
// L(i, 1, top) {
// cout << dis[pos[i]] << ' ';
// }
// cout << '\n';
node qwq;
ll ans = 1e18;
ll mxd = 0;
int rt = 0;
L(i, 0, top) {
if(i) {
if(!rt) rt = pos[i];
else rt = st.lca(rt, pos[i]);
mxd = max(mxd, st.dep[pos[i]]);
}
ll win = rt ? mxd - st.dep[rt] : 0;
ans = min(ans, max(i == top ? 0LL : dis[pos[i + 1]], win));
}
cout << ans << '\n';
}
L(i, 1, n) {
e[i].clear();
}
st.clear();
}
int main() {
ios :: sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int t; cin >> t; while(t--) Main();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 61248kb
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: 874ms
memory: 96660kb
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