QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360858#7103. Red Black TreeYeongTreeAC ✓632ms29080kbC++142.2kb2024-03-22 12:18:492024-03-22 12:18:50

Judging History

你现在查看的是最新测评结果

  • [2024-03-22 12:18:50]
  • 评测
  • 测评结果:AC
  • 用时:632ms
  • 内存:29080kb
  • [2024-03-22 12:18:49]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <set>
#include <map>
#include <random>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii array<int, 3>
#define tiiii array<int, 4>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
typedef long long ll;
const ll INF = (ll)1e18 + 7;

using namespace std;

vector<pii> gph[101010];
bool R[101010];
int dep[101010];
ll wdep[101010];
int sp[101010][20];
pll dis[101010];

void dfs(int x, int p, int d, ll wd, pll r)
{
	dep[x] = d;
	wdep[x] = wd;
	sp[x][0] = p;
	dis[x] = r;
	for(auto [y, w] : gph[x]) if(p != y) dfs(y, x, d + 1, wd + w, (R[y] ? pll{y, 0} : pll{r.ff, r.ss + w}));
}

int lca(int x, int y)
{
	if(dep[x] > dep[y]) swap(x, y);
	for(int i = 19; i >= 0; --i) if(dep[x] + (1 << i) <= dep[y]) y = sp[y][i];
	for(int i = 19; i >= 0; --i) if(sp[x][i] != sp[y][i]) x = sp[x][i], y = sp[y][i];
	return (x == y ? x : sp[x][0]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int T; cin >> T;
	while(T--)
	{
		int n, m, T; cin >> n >> m >> T;
		for(int i = 0; i < n; ++i) gph[i].clear(), R[i] = false;
		for(int i = 0; i < m; ++i)
		{
			int x; cin >> x; --x;
			R[x] = true;
		}
		for(int i = 1; i < n; ++i)
		{
			int x, y, w; cin >> x >> y >> w; --x; --y;
			gph[x].push_back({y, w});
			gph[y].push_back({x, w});
		}
		dfs(0, 0, 0, 0, pll{0, 0});
		for(int j = 1; j < 20; ++j) for(int i = 0; i < n; ++i) sp[i][j] = sp[sp[i][j - 1]][j - 1];

		while(T--)
		{
			int k; cin >> k;
			int A[k]; for(auto &i : A) cin >> i, --i;
			
			pll mx = {-1, 0};
			for(auto i : A) mx = max(mx, pll{dis[i].ss, i});

			vector<pll> V;
			ll pmx = 0;
			for(auto i : A)
			{
				if(dis[mx.ss].ff == dis[i].ff) V.push_back({wdep[lca(mx.ss, i)], dis[i].ss});
				else pmx = max(pmx, dis[i].ss);
			}

			sort(V.begin(), V.end());

			ll ans = INF;
			for(auto [l, x] : V)
			{
				ans = min(ans, max(wdep[mx.ss] - l, pmx));
				pmx = max(pmx, x);
			}

			cout << ans << '\n';
		}
	}
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 9772kb

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: 632ms
memory: 29080kb

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