QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#638400#7103. Red Black TreeDelovAC ✓1180ms27608kbC++173.8kb2024-10-13 15:50:162024-10-13 15:50:18

Judging History

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

  • [2024-10-13 15:50:18]
  • 评测
  • 测评结果:AC
  • 用时:1180ms
  • 内存:27608kb
  • [2024-10-13 15:50:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)

using i64 = long long;

const int N = 1e5 + 5;

int n, m, q;
int isred[N];
vector<pair< int, int> > e[N];
int fa[N][20], lg[N], dep[N], cntred[N];
i64 dis[N];

void clear() {
	for (int i = 1; i <= n; i ++) e[i].clear(), isred[i] = 0, dis[i] = 0;
	for (int i = 1; i <= n; i ++) 
		for (int j = 0; j <= 19; j ++) fa[i][j] = 0;
}

void dfs1(int x, int fx) {
	fa[x][0] = fx;
	dep[x] = dep[fx] + 1;
	cntred[x] = cntred[fx] + isred[x];
	for (int i = 1; i <= lg[dep[x]]; i ++)
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for (auto [y, w] : e[x]) if (y != fx) dis[y] = dis[x] + w, dfs1 (y, x);
}

void jump(int &x, i64 lim) {
	i64 disdown = dis[x];
	for (int i = lg[dep[x]]; i >= 0; i --)
		if (fa[x][i] && disdown - dis[fa[x][i]] <= lim)
			x = fa[x][i];
}

int lca(int x, int y) {
	if (dep[x] < dep[y]) swap (x, y);
	while (dep[x] > dep[y]) {
		x = fa[x][lg[dep[x] - dep[y]]];
	}
	if (x == y) return x;
	for (int i = lg[dep[x]]; i >= 0; i --)
		if (fa[x][i] ^ fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

void jumpa(int &x) {
	for (int i = lg[dep[x]]; i >= 0; i --) {
		if (fa[x][i] && (cntred[x] - cntred[fa[x][i]]) == 0 && isred[fa[x][i]] == 0)
			x = fa[x][i]; 	
	}
	if (isred[fa[x][0]]) x = fa[x][0];
}

void solve_one_query() {
	int k;
	cin >> k;
	vector<tuple<int, int, i64> > nodes(k);
	for (auto &[x, y, w] : nodes) {
		cin >> x, y = x, jumpa(y);
		if (isred[y]) w = dis[x] - dis[y];
		else w = 1e18;
	}
	
	vector<tuple<int, int, i64> > nodes_tmp;
	for (auto &[x, y, w] : nodes) {
		if (isred[x] == 0) nodes_tmp.push_back ({x, y, w} );
	}
	
	nodes = nodes_tmp;
	k = nodes_tmp.size();
	
	sort (nodes.begin(), nodes.end(), [&] (auto x, auto y) {
		return std :: get<2> (x) < std :: get<2> (y); 
	} );
	
	vector<int> suf_lca(k);
	vector<i64> suf_max(k);
	for (int i = k - 1; i >= 0; i --) {
		suf_lca[i] = get<0> (nodes[i]);
		suf_max[i] = dis[get<0> (nodes[i])];
		if (i != k - 1) 
			suf_lca[i] = lca (suf_lca[i], suf_lca[i + 1]), 
			suf_max[i] = max (suf_max[i], suf_max[i + 1]);
	}
	
	auto check = [&] (i64 maxlen) -> int {
		for (int i = 0; i <= k - 1; i ++)
			if (get<2> (nodes[i]) > maxlen) {
				if (dis[suf_lca[i]] + maxlen >= suf_max[i])
					return true;
				else
					return false;
			}
		return true;
	} ;
	
	i64 l = 0, r = 1e14, res = 1e14;
	while (l <= r) {
		i64 mid = (l + r) >> 1;
		if (check (mid)) r = mid - 1, res = mid;
		else l = mid + 1;
	}
	
	cout << res << '\n';
	
	/*
	
	auto check = [&] (i64 maxlen) -> int {
		vector<int> upnodes = nodes;
		for (int &x : upnodes) jump(x, maxlen);
		vector<int> limnode;
		
		int lc = -1;
		int deep_y = 1;
		
		for (int i = 0; i < k; i ++) {
			int x = nodes[i], y = upnodes[i];
			if ((cntred[x] - cntred[y]) == 0 && ! isred[y]) {
				// have lim
				if (dis[y] > dis[deep_y]) deep_y = y;
				if (lc == -1) lc = x;
				else lc = lca (lc, x);
			}
			else continue;
		}
		
		if (lc == -1 || dep[lc] >= dep[deep_y]) return true;
		else return false;
	} ;
	
	i64 l = 0, r = 1e14, res = 1e14;
	while (l <= r) {
		i64 mid = (l + r) >> 1;
		if (check (mid)) r = mid - 1, res = mid;
		else l = mid + 1;
	}
	
	cout << res << '\n'; */
}

void solve() {
	clear();
	cin >> n >> m >> q;
	lep (i, 1, m) {
		int x;
		cin >> x;
		isred[x] = 1;
	}
	lep (i, 2, n) {
		int x, y, w;
		cin >> x >> y >> w;
		e[x].push_back ( {y, w} );
		e[y].push_back ( {x, w} );
	}
	lep (i, 2, n) lg[i] = lg[i >> 1] + 1;
	dfs1 (1, 0);
	//q = 1;
	while (q --) solve_one_query();
}

int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int Case;
	cin >> Case; //Case = 1;
	while (Case --) solve();
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7664kb

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: 1180ms
memory: 27608kb

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