QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300821#7103. Red Black TreekasrataWA 1345ms28472kbC++202.9kb2024-01-08 21:01:302024-01-08 21:01:31

Judging History

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

  • [2024-01-08 21:01:31]
  • 评测
  • 测评结果:WA
  • 用时:1345ms
  • 内存:28472kb
  • [2024-01-08 21:01:30]
  • 提交

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;
	}
}

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 cmp(int u, int v) {
	return h[lca(u, leaf)] > h[lca(v, leaf)];
}

int cal(vi vec, int k) {
	if (k == 1)
		return 0;
	sort(vec.begin(), vec.end(), [] (int u, int v) {return dis[u].S > dis[v].S;});
	if (dis[vec[0]].S == dis[vec[1]].S && dis[vec[0]].F != dis[vec[1]].F)
		return dis[vec[0]].S;
	vi vc;
	set<pair<ll, int>> s;
	ll mx_out = 0;
	leaf = vec[0], root = dis[leaf].F;
	for (int v: vec)
		if (isPar(root, lca(leaf, v))) 
			vc.pb(v), s.insert({-dis[v].S, v});
		else 
			mx_out = max(mx_out, dis[v].S);
	sort(vc.begin(), vc.end(), cmp);
	vector<int> tt;
	int t = leaf;
	ll mn = 1e18, mx1 = 0;
	for (int v: vc) 
		if (lca(v, leaf) == t)
			tt.push_back(v);
		else {
			for (int u: tt) {
				s.erase({-dis[u].S, u});
				mx1 = max(mx1, hw[u] - hw[t]);
			}
			ll w = 0;
			if (!s.empty())
				w = -((*s.begin()).F);
			mn = min(mn, max({mx1, mx_out, w}));
			tt.clear();
			mx1 += hw[t] - hw[lca(v, leaf)];
			t = lca(v, leaf);
			tt.pb(v);
		}
	for (int u: tt) {
		s.erase({-dis[u].S, u});
		mx1 = max(mx1, hw[u] - hw[t]);
	}
	mn = min(mn, max(mx1, mx_out));
	return mn;
}

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();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1345ms
memory: 28472kb

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
894940447
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

wrong answer 18th lines differ - expected: '785245841', found: '894940447'