QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200838#7103. Red Black Treey_kx_bML 2ms11712kbC++144.7kb2023-10-04 21:14:222023-10-04 21:14:23

Judging History

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

  • [2023-10-04 21:14:23]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:11712kb
  • [2023-10-04 21:14:22]
  • 提交

answer

// Problem: B. Red Black Tree
// Contest: undefined - The 2nd Universal Cup. Stage 1: Qingdao
// URL: https://qoj.ac/contest/1339/problem/7103
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// [20:14:34] [Companion] [未知的属性: [group]。请在 %2 检查头部注释的设置。]
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define gc getchar
#define itn int
#define x first
#define y second
#define eb emplace_back
#define em emplace
#define pb push_back
#define db double
#define y1 yy1_yyds
using namespace std; typedef long long ll; typedef unsigned long long ull;
// https://www.luogu.com.cn/discuss/522581 About "const"
ll read() {
	ll x = 0; short fh = 1; char ch = gc();
	while (!isdigit(ch)) {
		if (ch == '-') fh = -1;
		if (ch < 10) exit(0); 
		ch = gc();
	}
	while (isdigit(ch))
		x = x * 10 + (ch ^ 48), ch = gc();
	return fh * x;
}
#ifndef ONLINE_JUDGE
void debug() {cerr << "\n";}
template<typename Typ1> void debug(Typ1 arg) {cerr << arg << "\n";}
template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {
	cerr << arg << " ", debug(args...);
}
#else
void debug() {}
template<typename Typ1> void debug(Typ1 arg) {}
template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {}
#endif
void writeln(ll arg) {printf("%lld\n", arg);}
template<typename ...Typ2> void writeln(ll arg, Typ2 ...args) {
	printf("%lld ", arg), writeln(args...);
}
typedef pair <int, int> pii; typedef pair <ll, ll> pll;
const char Y_E_S[] = "YES", N__O[] = "NO";
// const char Y_E_S[] = "Yes", N__O[] = "No";
// #define infinite_testcase
#define multiple_testcase
// #define output_Yes_No
const int DUST = 327, N = 114514, M = -1;
int head[N], to[N << 1], ne[N << 1], w[N << 1], idx1 = 0;
void add(int u, int v, int W = 1) {
    w[idx1] = W, to[idx1] = v, ne[idx1] = head[u], head[u] = idx1++;
}
void addd(int u, int v, int W = 1) {add(u, v, W), add(v, u, W);}
int fa[N], dph[N], siz[N], son[N], top[N], dfn[N], id[N];
void dfs1(int u, int f) {
    fa[u] = f, dph[u] = dph[f] + 1, siz[u] = 1;
    for(int e = head[u], v; ~e; e = ne[e]) if((v = to[e]) != f) {
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
int timer = 0;
void dfs2(int u, int tp) {
    top[u] = tp;
    // dfn[u] = ++timer;
    // id[timer] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int e = head[u], v; ~e; e = ne[e]) if((v = to[e]) != fa[u] && v != son[u])
        dfs2(v, v);
}
int lca(int u, int v) {
    while(top[u] != top[v]) {
        if(dph[top[u]] < dph[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    if(dph[u] > dph[v]) swap(u, v);
    return u;
}

bool red[N];
ll cost[N];//预处理每个点到祖先红节点的距离
ll upw[N];
void dfs0(int u, int f) {
	if(red[u]) cost[u] = 0;
	for(int e = head[u], v; ~e; e = ne[e]) if((v = to[e]) != f) {
		cost[v] = cost[u] + w[e];
		upw[v] = upw[u] + w[e];
		dfs0(v, u);
	}
}
ll dis(int f, int v) {return upw[v] - upw[f];}
pll p[N];
bool major(int Case = 1) {
	int n = read(), m = read(), q = read();
	memset(red, 0, n);
	memset(head, -1, (n + 1) << 2); idx1 = 0;
	for(int i = 1; i <= m; i++) red[read()] = 1;
	assert(red[1]);
	for(int i = 1; i < n; i++) {
		int u = read(), v = read(), W = read();
		addd(u, v, W);
	}
	dfs0(1, 0); dfs1(1, 0); dfs2(1, 1);
	while(q--) {
		int k = read();
		for(int i = 1; i <= /*n*/k; i++) p[i].x = cost[p[i].y = read()];
		sort(p + 1, p + k + 1, greater<pll>());
		p[k + 1].x = 0;
		int u = p[1].y;
/*不是 int*/ll res = 0, ans = p[2].x;// res: 当前移动的红点到
		for(int i = 2; i <= k; i++) {
			int v = lca(u, p[i].y);
			res = max(res + dis(v, u), dis(v, p[i].y));
			ans = min(ans, max(res/**/, p[i + 1].x));
		/**/u = v;
		}
		writeln(ans);
	}
	return Case ^= Case ^ Case;
}
void initial_function(int argc, char **argv) {
	**argv = argc; /* <- place_holder
	you won't give up no matter what happens, will you?
	code time: 
	---
	
	贪心先把cost最大的点改成红。
	然后考虑第二大的节点,尝试把这个红点往上移到 lca 处。
	如此循环直到无法产生贡献
	(节点距这个移动的红点中间还有红点 or 红点没有对一开始的节点产生贡献)为止。(其实也不需要停止?)
	(?)
	*/
}
signed main(int argc, char **argv) {
	initial_function(argc, argv);
	int Case = 1, Maxcase = 1;
	for (
#ifdef multiple_testcase
		  Maxcase = read()
#endif
				     	  ;
#ifndef infinite_testcase
							Case <= Maxcase
#endif
				     					   ; Case++)
#ifdef output_Yes_No
		puts(major(Case) ? Y_E_S : N__O);
#else
		major(Case);
#endif
	return DUST ^ 0x147;
}


详细

Test #1:

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

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
Memory 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: