QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#637955#7103. Red Black TreeDelovTL 0ms9996kbC++172.5kb2024-10-13 14:28:182024-10-13 14:28:18

Judging History

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

  • [2024-10-13 14:28:18]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:9996kb
  • [2024-10-13 14:28:18]
  • 提交

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 solve_one_query() {
	int k;
	cin >> k;
	vector<int> nodes(k);
	for (int &x : nodes) cin >> x;

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

詳細信息

Test #1:

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

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:

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: