QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107659 | #5418. Color the Tree | gtm1514 | WA | 38ms | 3660kb | C++14 | 2.9kb | 2023-05-22 11:55:13 | 2023-05-22 11:55:18 |
Judging History
answer
/*你说的对,但是大样例呢*/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#define int long long
using namespace std;
int n,a[100010];
struct ST{
int st[100010][21];
void build(){
for(int i=0;i<n;i++)st[i][0]=a[i];
for(int j=1;j<__lg(n);j++){
for(int i=0;i+(1<<j)-1<n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
}
int query(int l,int r){
int k=__lg(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
}st;
struct node{
int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int dep[100010],son[100010],sec[100010];
void dfs1(int x,int f){
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs1(edge[i].v,x);
if(dep[son[x]]<dep[edge[i].v])sec[x]=dep[son[x]],son[x]=edge[i].v;
else if(sec[x]<dep[edge[i].v])sec[x]=dep[edge[i].v];
}
}
sec[x]++;
dep[x]=dep[son[x]]+1;
}
int buf1[100010],*dp[100010],*now1=buf1;
int buf2[100010],*lz[100010],*now2=buf2;
void dfs2(int x,int f){
if(son[x]){
dp[son[x]]=dp[x]+1;lz[son[x]]=lz[x]+1;
dfs2(son[x],x);
}
dp[x][0]=a[0];
for(int i=1;i<sec[x];i++)dp[x][i]=min(dp[x][i],st.query(lz[x][i],i));
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f&&edge[i].v!=son[x]){
dp[edge[i].v]=now1;now1+=dep[edge[i].v];
lz[edge[i].v]=now2;now2+=dep[edge[i].v];
dfs2(edge[i].v,x);
for(int j=1;j<=dep[edge[i].v];j++){
dp[edge[i].v][j-1]=min(dp[edge[i].v][j-1],st.query(lz[edge[i].v][j-1],j));
dp[x][j]+=dp[edge[i].v][j-1];
}
}
}
for(int i=0;i<sec[x];i++)dp[x][i]=min(dp[x][i],a[i]);
for(int i=0;i<sec[x];i++)lz[x][i]=i+1;
}
void clear(){
t=0;
for(int i=0;i<=n;i++)head[i]=son[i]=dep[i]=sec[i]=buf1[i]=buf2[i]=0;
for(int i=0;i<=__lg(n);i++)for(int j=0;j<n;j++)st.st[j][i]=0;
now1=buf1;now2=buf2;
}
signed main(){
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
int tim=1;
scanf("%lld",&tim);
while(tim--){
scanf("%lld",&n);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
st.build();
for(int i=1;i<n;i++){
int u,v;scanf("%lld%lld",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);
dp[1]=now1;now1+=dep[1];lz[1]=now2;now2+=dep[1];
dfs2(1,0);
int ans=0;
for(int i=0;i<sec[1];i++)ans+=dp[1][i];
for(int i=sec[1];i<dep[1];i++){
dp[1][i]=min(dp[1][i],st.query(lz[1][i],i));
ans+=dp[1][i];
}
printf("%lld\n",ans);
clear();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
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: 38ms
memory: 3612kb
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 168 222 230 156 240 225 126 100 81 155 73 154 127 149 124 228 230 132 187 153 170 78 282 195 286 191 211 119 197 211 233 88 252 239 233 173 180 195 121 109 148 180 175 226 210 182 97 199 59 56 31 115 204 203 172 139 208 43 140 189 170 173 137 233 94 163 273 80 350 156 133 146 159 240 269 137 222...
result:
wrong answer 59th numbers differ - expected: '53', found: '43'