QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#148669 | #5418. Color the Tree | 11d10xy | WA | 35ms | 9628kb | C++14 | 1.4kb | 2023-08-23 17:21:36 | 2023-08-23 20:25:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int>G[100010];
int n,mi[100010][25],mxdis[100010],dfn[100010],las[100010],tot;
ll f[100010];
auto query=[](int l,int r){int g=__lg(r-l+1);return min(mi[l][g],mi[r-(1<<g)+1][g]);};
void dfs(int u,int fa){
if(fa)G[u].erase(find(begin(G[u]),end(G[u]),fa));
for(int&v:G[u]){
dfs(v,u);
if(mxdis[v]+1>mxdis[u])
mxdis[u]=mxdis[v]+1,swap(v,G[u][0]);
}
}
auto upd=[](int ind,int now){if(las[ind]<=now)f[ind]=min(f[ind],(ll)query(las[ind],now)),las[ind]=now+1;return f[ind];};
void solve(int u){
dfn[u]=++tot;
for(int v:G[u]){
solve(v);
if(v!=G[u][0])
for(int i=0;i<=mxdis[v];i++){
upd(dfn[u]+i+1,i);
f[dfn[u]+i+1]+=upd(dfn[v]+i,i);
}
}
}
int main(){
int T;for(cin>>T;T--;){
cin>>n;
for(int i=1;i<=n;i++)dfn[i]=mxdis[i]=las[i]=0,f[i]=1e18,G[i].clear();
for(int i=0;i<n;i++)scanf("%d",&mi[i][0]);
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
for(int i=1;i<=20;i++)
for(int j=0;j+(1<<i)<=n;j++)
mi[j][i]=min(mi[j][i-1],mi[j+(1<<i-1)][i-1]);
dfs(1,0),solve(1);
ll ans=0;
for(int i=0;i<=mxdis[1];i++)ans+=upd(i+1,i);
cout<<ans<<endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9348kb
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: 35ms
memory: 9628kb
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 92 131 179 127 221 205 104 100 79 139 68 129 91 142 79 153 176 104 127 111 90 75 173 174 90 116 154 30 87 54 152 63 240 197 143 150 169 121 112 78 72 165 123 217 144 122 73 81 59 56 22 115 131 165 63 95 163 50 95 94 88 159 119 190 58 151 199 80 294 142 56 82 144 197 207 72 121 65 192 84 62 99 91...
result:
wrong answer 2nd numbers differ - expected: '168', found: '92'