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 |
---|---|---|---|---|---|---|---|---|---|
#585941 | #7103. Red Black Tree | Tomorrow | WA | 824ms | 57008kb | C++20 | 2.9kb | 2024-09-23 23:16:59 | 2024-09-23 23:17:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define C const
#define U unsigned
#define SC static
#define CE constexpr
#define TL template
#define TN typename
#define OP operator
#define pb push_back
#define ft first
#define sd second
#define mi (l + (r - l) / 2)
#define TTT TL<TN T = I>
#define TTI TL<TN It>
#define BE(v) v.begin(), v.end()
#define VD void
#define BL bool
#define CH char
#define I int
#define LL long long
#define II __int128
#define D double
using PII = pair<I, I>;
TTT using V = vector<T>;
#define FORX(v) for(auto& x : v)
#define FOR(i, b, e) for(auto i = b, _e = (decltype(i))e;i < _e; ++i)
#define FORR(i, b, e) for(auto i = b, _e = (decltype(i))e;i > _e; --i)
#define FORV(v, i) for (I i = 0, _n = v.size(), x = _n ? v[0] : 0;i < _n;x = v[++i])
#define FUNC(T, f, ...) function<T(__VA_ARGS__)> f = [&](__VA_ARGS__)->T
#define DR(T, ...) T __VA_ARGS__; R(__VA_ARGS__);
TTT VD R(T& x) { cin >> x; }
TTT T R() { DR(T, x); return x; }
TL<TN T, TN... A> VD R(T& x, A&... a) { R(x), R(a...); }
CE CH LF = '\n', SP = ' ';
TL<CH s = LF> VD W() { cout << s; }
TL<CH s = LF, TN T> VD W(C T& x) { cout << x << s; }
TL<CH s = LF, TN T, TN... A> VD W(C T& x, C A&... a) { W<SP>(x), W<s>(a...); }
TTT CE T inf() { return numeric_limits<T>::max() / 2; }
TTT VD setmin(T& a, C T& b) { if (b < a)a = b; }
TTT VD setmax(T& a, C T& b) { if (a < b)a = b; }
struct LCA
{
I n, d; V<V<PII>> a{ {} }; V<I> id;
LCA(V<V<I>>& e, I rt = 1) :id(e.size())
{
FUNC(VD, dfs, I p, I fa, I dp)
{
id[p] = a[0].size(), a[0].pb({ dp,p });
FORX(e[p])if (x != fa)dfs(x, p, dp + 1), a[0].pb({ dp,p });
};
dfs(rt, -1, 0);
n = a[0].size(); d = ilogb(n); a.resize(d + 1, V<PII>(n));
FOR(k, 0, d)FOR(i, 0, n - (1 << k))a[k + 1][i] = min(a[k][i], a[k][i + (1 << k)]);
}
I OP()(I x, I y)
{
if (id[x] > id[y])swap(x, y);
x = id[x], y = id[y] + 1; I k = ilogb(y - x);
return min(a[k][x], a[k][y - (1 << k)]).sd;
}
};
VD test()
{
DR(I, n, m, q); ++n;
V<I> isr(n), is(n); V<LL> dp(n), md(n);
V<V<I>> e(n); V<V<LL>> g(n);
while (m--)isr[R<I>()] = 1;
FOR(i, 2, n)
{
DR(I, u, v, w);
e[u].pb(v), g[u].pb(w);
e[v].pb(u), g[v].pb(w);
}
LCA lca(e);
FUNC(VD, dfs, I p, I fa)
{
FORV(e[p], i)
{
if (x == fa)continue;
dp[x] = dp[p] + g[p][i];
if (!isr[x])md[x] = md[p] + g[p][i];
dfs(x, p);
}
};
dfs(1, 0);
while (q--)
{
DR(I, k);V<I> a(k); FORX(a)R(x);
sort(BE(a), [&](I x, I y) {return md[x] > md[y];});
I p = a[0]; LL ans = md[a[0]];
FOR(i, 1, k)
{
p = lca(p, a[i-1]);
setmin(ans, max(dp[a[0]] - dp[p], md[a[i]]));
}
W(ans);
}
}
I main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if (fopen("test.in", "r"))
{
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
}
I t = 1;
R(t);
while (t--)test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
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: 824ms
memory: 57008kb
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 66903787 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 57081624 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164...
result:
wrong answer 3rd lines differ - expected: '0', found: '66903787'