QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179987#7103. Red Black Treenotyour_youngWA 818ms35428kbC++171.8kb2023-09-15 14:13:242023-09-15 14:13:24

Judging History

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

  • [2023-09-15 14:13:24]
  • 评测
  • 测评结果:WA
  • 用时:818ms
  • 内存:35428kb
  • [2023-09-15 14:13:24]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
using  i64 = long long;
using PII = pair<i64, int>;
const int N = 1e5 + 10;
int n, m, q;
vector<PII> g[N];
bool red[N];
i64 fa[N][17], dep[N], dis[N], dr[N];
i64 dfn[N], cnt;
void dfs(int u, int father)
{
	dfn[u] = ++ cnt;
	dep[u] = dep[father] + 1;
	fa[u][0] = father;
	for(int k = 1;k < 17;k ++)
		fa[u][k] = fa[fa[u][k - 1]][k - 1];

	if(red[u])
		dr[u] = 0;

	for(auto [v, w] : g[u])
	{
		if(v == father)
			continue;
		dis[v] = dis[u] + w;
		dr[v] = dr[u] + w;
		dfs(v, u);
	}
}

int lca(int a, int b)
{
	if(a == -1)
		return 1;
	 if(dep[a] < dep[b])
	 	swap(a, b);

	 for(int k = 16;k >= 0;k --)
	 	if(dep[fa[a][k]] >= dep[b])
	 		a = fa[a][k];

	 if(a == b)
	 	return a;

	 for(int k = 16;k >= 0;k --)
	 	if(fa[a][k] != fa[b][k])
	 		a = fa[a][k], b = fa[b][k];

	 return fa[a][0];
}

void solve()
{
	cin >> n >> m >> q;
	for(int i = 1, v;i <= m;i ++)
		cin >> v, red[v] = true;

	for(int i = 1;i < n;i ++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}

	dfs(1, 0);

	while(q --)
	{
		int k;
		cin >> k;
		vector<int> v(k);
		for(int & x : v)
			cin >> x;
		sort(v.begin(), v.end(), [&](int a, int b) {
			return dr[a] > dr[b];
		});

		i64 res = dr[v[0]], mx = dis[v[0]];
		int anc = v[0];
		for(int i = 0;i + 1 < v.size();i ++)
		{
			anc = lca(anc, v[i]);
			mx = max(mx, dis[v[i]]);
			res = min(res, max(dr[v[i + 1]], mx - dis[anc]));

		}

		cout << res << endl;
	}

	for(int i = 1;i<= n;i ++)
		red[i] = false, g[i].clear();
	cnt = 0;

}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int tc;
	cin >> tc;
	while(tc --)
		solve();
	return 0;
}

详细

Test #1:

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

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: 818ms
memory: 35428kb

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'