QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179490 | #5418. Color the Tree | 0x4F5DA2 | WA | 28ms | 13828kb | C++14 | 5.4kb | 2023-09-14 21:49:51 | 2023-09-14 21:49:51 |
Judging History
answer
#include <cstdio>
#include <algorithm>
const int maxn = 100000;
const long long LLF = 10000000000000000;
const int maxlog = 17;
struct node1{
int nxt;
int to;
}edge[maxn * 2 + 10];
int head[maxn + 10];
int top;
void add_e(int u, int v){
++top;
edge[top].nxt = head[u];
edge[top].to = v;
head[u] = top;
return ;
}
int n;
int st[maxlog + 1][maxn + 10];
int log_2[maxn + 10];
int get_mina(int l, int r){
int len = r - l + 1;
int lg = log_2[len];
return std::min(st[lg][l], st[lg][r - (1 << lg) + 1]);
}
int dep[maxn + 10];
int max_dep;
int dfn[maxn + 10];
int top_dfn;
int fa[maxn + 10][maxlog + 1];
//存每个深度的点
node1 edge2[maxn + 10];
int head2[maxn + 10];
int top2;
void add_e2(int u, int v){
++top2;
edge2[top2].nxt = head2[u];
edge2[top2].to = v;
head2[u] = top2;
}
//存虚树
node1 edge3[maxn + 10];
int head3[maxn + 10];
int top3;
void add_e3(int u, int v){
//printf("%d->%d\n", u, v);
++top3;
/*if(head3[u] == top3){
printf("cnm, %d, %d\n", u, v);
}*/
edge3[top3].nxt = head3[u];
edge3[top3].to = v;
head3[u] = top3;
}
void dfs1(int x){
dep[x] = dep[fa[x][0]] + 1;
if(max_dep < dep[x])
max_dep = dep[x];
add_e2(dep[x], x);
/*if(dep[x] == 5)
printf("%d->%d\n", dep[x], x);*/
dfn[x] = ++top_dfn;
for(int i = head[x]; i; i = edge[i].nxt){
int y = edge[i].to;
if(y != fa[x][0]){
fa[y][0] = x;
dfs1(y);
}
}
}
int LCA(int x, int y){
if(dep[x] < dep[y]){
int temp = x;
x = y;
y = temp;
}
for(int i = maxlog; i >= 0; --i){
if(dep[x] - (1 << i) >= dep[y]){
x = fa[x][i];
}
}
if(x == y)
return x;
for(int i = maxlog; i >= 0; --i){
if(fa[x][i] != fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int key_node[maxn + 10];
int top_key;
bool cmp(int a, int b){
return dfn[a] < dfn[b];
}
int sta[maxn + 10];
int tops;
long long ans[maxn + 10];
long long dp[maxn + 10];
int now_d;
void dfs2(int x, int fa){
if(dep[x] == now_d){
dp[x] = (long long)get_mina(now_d - dep[fa] - 1, now_d - dep[x]);
return ;
}
long long temp = 0;
for(int i = head3[x]; i; i = edge3[i].nxt){
int y = edge3[i].to;
//printf("%d:%d\n", i, edge3[i].nxt);
//printf("%d->%d\n", x, y);
dfs2(y, x);
temp = temp + dp[y];
}
dp[x] = std::min((long long)get_mina(now_d - dep[fa] - 1, now_d - dep[x]), temp);
return ;
}
int main(){
log_2[1] = 0;
for(int i = 2; i <= maxn; ++i){
log_2[i] = log_2[(i >> 1)] + 1;
}
int T;
scanf("%d", &T);
// if(T == 3000)
// T = 1;
while(T--){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", &st[0][i]);
}
for(int i = 1; i <= maxlog; ++i){
for(int j = 0; j + (1 << i) - 1 < n; ++j){
st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
/*if(T == 3000){
return 0;
}*/
int u, v;
for(int i = 1; i < n; ++i){
scanf("%d%d", &u, &v);
/*if(T == 2999 && i > 26){
printf("#%d %d\n", u, v);
}*/
add_e(u, v);
add_e(v, u);
}
/*if(T == 2999){
return 0;
}*/
fa[1][0] = 0;
dfs1(1);
for(int i = 1; i <= maxlog; ++i){
for(int j = 1; j <= n; ++j){
fa[j][i] = fa[fa[j][i - 1]][i - 1];
}
}
/*while(1){
scanf("%d%d", &u, &v);
printf("%d\n", LCA(u, v));
}*/
long long final_ans = 0;
for(int i = 1; i <= max_dep; ++i){
//建立虚树
top_key = 0;
tops = 0;
for(int j = head2[i]; j; j = edge2[j].nxt){
++top_key;
key_node[top_key] = edge2[j].to;
}
std::sort(key_node + 1, key_node + 1 + top_key, cmp);
++tops;
sta[tops] = 1;
head3[1] = 0;
for(int j = 1; j <= top_key; ++j){
if(key_node[j] == 1)
continue ;
int l = LCA(key_node[j], sta[tops]);
if(l != sta[tops]){
while(dfn[l] < dfn[sta[tops - 1]]){
add_e3(sta[tops - 1], sta[tops]);
--tops;
}
if(dfn[l] > dfn[sta[tops - 1]]){
head3[l] = 0;
add_e3(l, sta[tops]);
sta[tops] = l;
}
else{
add_e3(l, sta[tops]);
--tops;
}
}
head3[key_node[j]] = 0;
++tops;
sta[tops] = key_node[j];
}
for(int j = 1; j < tops; ++j){
add_e3(sta[j], sta[j + 1]);
}
//debug
/*printf("%d:\n", i);
for(int j = 1; j <= top_key; ++j){
printf("%d ", key_node[j]);
}
putchar('\n');
for(int j = 1; j <= tops; ++j){
printf("%d ", sta[j]);
}
putchar('\n');*/
//计算
now_d = i;
dfs2(1, 0);
final_ans = final_ans + dp[1];
//清空
top3 = 0;
/*head3[1] = 0;
for(int j = 1; j <= top_key; ++j){
head3[key_node[j]] = 0;
}*/
}
printf("%lld\n", final_ans);
//清空
top2 = 0;
for(int i = 1; i <= max_dep; ++i)
head2[i] = 0;
top = 0;
for(int i = 1; i <= n; ++i){
head[i] = 0;
}
max_dep = 0;
top_dfn = 0;
}
return 0;
}
/*
1
54
43 44 11 49 17
14 7 30 35 12
34 14 15 8 29
47 30 31 39 17
26 23 26 45 34
50 49 13 35 18
29 15 13 44 47
5 22 20 19 46
30 22 26 13 47
46 43 27 48 48
13 14 30 44
1 2
1 3
2 4
3 5
4 6
2 7
4 8
1 9
3 10
1 11
8 12
2 13
9 14
1 15
1 16
15 17
15 18
7 19
1 20
19 21
13 22
10 23
17 24
9 25
9 26
24 27
8 28
13 29
10 30
18 31
4 32
9 33
27 34
20 35
32 36
9 37
31 38
38 39
13 40
3 41
41 42
5 43
38 44
12 45
2 46
37 47
12 48
18 49
48 50
33 51
28 52
25 53
16 54
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9816kb
input:
3 4 10 15 40 1 1 2 2 3 2 4 5 10 5 1 100 1000 1 2 2 3 2 4 4 5 4 1000 200 10 8 1 2 2 3 3 4
output:
35 17 1218
result:
ok 3 number(s): "35 17 1218"
Test #2:
score: -100
Wrong Answer
time: 28ms
memory: 13828kb
input:
3000 54 43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44 1 2 1 3 2 4 3 5 4 6 2 7 4 8 1 9 3 10 1 11 8 12 2 13 9 14 1 15 1 16 15 17 15 18 7 19 1 20 19 21 13 22 10 23 17 24 9 25 9 26 24 27 8 28...
output:
180 180 224 237 161 273 225 145 105 87 165 87 168 154 193 142 251 230 153 233 153 171 80 282 234 286 204 211 119 203 211 234 88 252 239 240 199 184 217 129 109 164 195 201 226 210 182 139 243 59 56 31 127 209 203 172 173 225 53 144 189 174 175 141 233 107 181 273 80 394 161 133 157 159 240 281 146 2...
result:
wrong answer 2nd numbers differ - expected: '168', found: '180'