QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#585941#7103. Red Black TreeTomorrowWA 824ms57008kbC++202.9kb2024-09-23 23:16:592024-09-23 23:17:00

Judging History

This is the latest submission verdict.

  • [2024-09-23 23:17:00]
  • Judged
  • Verdict: WA
  • Time: 824ms
  • Memory: 57008kb
  • [2024-09-23 23:16:59]
  • Submitted

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'