QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179504 | #5418. Color the Tree | 0x4F5DA2 | WA | 2ms | 11808kb | C++14 | 5.6kb | 2023-09-14 21:54:12 | 2023-09-14 21:54:12 |
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);
/*if(T == 2998)
printf("%d\n", n);*/
for(int i = 0; i < n; ++i){
scanf("%d", &st[0][i]);
/*if(T == 2998)
printf("%d ", st[0][i]);*/
}
/*if(T == 2998)
putchar('\n');*/
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))]);
}
}
int u, v;
for(int i = 1; i < n; ++i){
scanf("%d%d", &u, &v);
if(T == 2998 && i > 66){
printf("%d %d\n", u, v);
}
add_e(u, v);
add_e(v, u);
}
if(T == 2998){
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
75
36 8 15 37 10 42 19 33 10 41 45 47 39 20 13 7 21 17 16 8 27 23 41 34 26 9 16 33 25 18 18 42 20 24 28 12 27 16 45 33 12 30 31 37 17 8 39 7 18 13 12 12 32 47 50 12 31 49 26 27 22 39 42 12 46 34 37 31 5 33 28 19 25 12 12
1 2
1 3
1 4
3 5
1 6
1 7
5 8
1 9
7 10
3 11
10 12
11 13
8 14
2 15
2 16
2 17
9 18
12 19
12 20
2 21
8 22
10 23
18 24
14 25
25 26
21 27
11 28
4 29
29 30
5 31
29 32
32 33
26 34
22 35
33 36
24 37
31 38
13 39
3 40
8 41
3 42
6 43
30 44
23 45
10 46
16 47
9 48
6 49
10 50
42 51
48 52
37 53
5 54
19 55
47 56
54 57
25 58
17 59
30 60
20 61
42 62
4 63
45 64
19 65
58 66
4 67
32 68
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11776kb
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: 2ms
memory: 11808kb
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 32 68 49 69 9 70 61 71 70 72 54 73 49 74 32 75
result:
wrong answer 2nd numbers differ - expected: '168', found: '32'