QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300940#7103. Red Black TreekasrataTL 0ms5856kbC++203.2kb2024-01-09 02:28:532024-01-09 02:28:53

Judging History

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

  • [2024-01-09 02:28:53]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:5856kb
  • [2024-01-09 02:28:53]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define F first
#define S second
#define pb push_back
#define ll long long
#define pil pair<int, ll>
#define pii pair<int, int> 
#define vi vector<int> 

const int N = 1e5 + 7, LG = 18;;
int n, m, q, s, leaf, root, h[N], st[N], en[N], red[N], spar[N][LG];
ll hw[N];
vector<pii> ad[N];
pil dis[N];

void rm() {
	s = 0;
	for (int i = 0; i < n; i++) {
		ad[i].clear();
		st[i] = en[i] = h[i] = hw[i] = 0;
		red[i] = false;
		for (int j = 0; j < LG; j++)
			spar[i][j] = 0;
		dis[i] = {0, 0};
	}
}

void input() {
	cin >> n >> m >> q;
	for (int i = 0, r; i < m; i++)
		cin >> r, r--, red[r] = true;
	for (int i = 0, u, v, w; i < n - 1; i++) {
		cin >> u >> v >> w, u--, v--;
		ad[u].pb({v, w}), ad[v].pb({u, w});
	}
}

void dfs(int v, int par, int who, ll len) {
	dis[v] = {who, len};
	st[v] = s++;
	for (auto [u, w]: ad[v])
		if (u != par) {
			spar[u][0] = v;
			hw[u] = hw[v] + w;
			h[u] = h[v] + 1;
			red[u]? dfs(u, v, u, 0): dfs(u, v, who, len + w);
		}
	en[v] = s;
}

bool isPar(int u, int v) {
	return st[v] >= st[u] && en[u] >= en[v];
}

int lca(int u, int v) {
	if (h[u] < h[v])
		swap(u, v);
	for (int j = LG - 1; j >= 0; j--)
		if ((1 << j) <= h[u] - h[v]) 
			u = spar[u][j];
	if (u == v)
		return v;
	for (int j = LG - 1; j >= 0; j--)
		if (spar[u][j] != spar[v][j])
			u = spar[u][j], v = spar[v][j];
	return spar[u][0];
}

bool cmp1(int u, int v) {
	return -dis[u].S < -dis[v].S;
}

bool cmp2(int u, int v) {
	return h[lca(u, leaf)] < h[lca(v, leaf)];
}

bool cmp3(int u, int v) {
	return h[u] < h[v];
}

vi uniq(vi v) {
	vi res;
	sort(v.begin(), v.end());
	res.pb(v[0]);
	for (int i = 1; i < (int) v.size(); i++)
		if (v[i] != v[i - 1])
			res.pb(v[i]);
	return res;
}

int cal(vi vec, int k) {
	if (k == 1)
		return 0;
	sort(vec.begin(), vec.end(), cmp1);
	if (dis[vec[0]].S == dis[vec[1]].S && dis[vec[0]].F != dis[vec[1]].F)
		return dis[vec[0]].S;
	vi vc;
	multiset<ll> s;
	vi row;
	ll mx_out = 0;
	leaf = vec[0], root = dis[leaf].F;
	for (int v: vec)
		if (dis[v].F == root) {
			int u = lca(v, leaf);
			vc.pb(v), s.insert(-dis[v].S), row.pb(u);
		}
		else 
			mx_out = max(mx_out, dis[v].S);
	row = uniq(row);
	sort(vc.begin(), vc.end(), cmp2), reverse(vc.begin(), vc.end());
	sort(row.begin(), row.end(), cmp3);
	ll mx1 = 0, mn = 1e18;
	for (int v: vc) {
		int u = row.back();
		if (lca(v, leaf) != u) {
			ll w = s.empty()? 0: -(*s.begin());
			mn = min(mn, max({mx1, mx_out, w}));
			row.pop_back();	
			if (row.empty())
				while (true);
			mx1 += hw[u] - hw[row.back()];
		}
		s.erase(s.find(-dis[v].S));
		mx1 = max(mx1, hw[v] - hw[row.back()]);
	}
	return min(mn, max(mx_out, mx1));
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	for (cin >> T; T; T--) {
		input(), dfs(0, -1, 0, 0);
		for (int i = 0; i < n; i++)
			for (int j = 1; j < LG; j++)
				spar[i][j] = spar[spar[i][j - 1]][j - 1];
		while (q--) {
			int k;
			cin >> k;
			vi v;
			for (int i = 0, u; i < k; i++) 
				cin >> u, u--, v.pb(u);
			cout << cal(v, k) << '\n';
		}
		rm();
	}
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5856kb

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
Time Limit Exceeded

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:


result: