QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#200842 | #7103. Red Black Tree | y_kx_b | AC ✓ | 288ms | 16272kb | C++14 | 4.7kb | 2023-10-04 21:18:48 | 2023-10-04 21:18:48 |
Judging History
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];
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 + 1);
memset(head, -1, (n + 1) << 2); idx1 = 0;
memset(son, 0, (n + 1) << 2);
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 红点没有对一开始的节点产生贡献)为止。(其实也不需要停止?)
(?)
哦树剖没清 son 数组,那没事了。
*/
}
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;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9948kb
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: 288ms
memory: 16272kb
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