QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177212 | #5418. Color the Tree | brz | WA | 36ms | 11732kb | C++20 | 2.8kb | 2023-09-12 17:51:44 | 2023-09-12 17:51:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define cn getchar
template<class TY>void read(TY &x){
x=0;int f1=1;char ch=cn();
while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
template<class TY>void write2(TY x){
if(x>9)write2(x/10);
putchar(x%10+'0');
}
template<class TY>void write(TY x){
if(x<0)putchar('-'),x=-x;
write2(x);
}
int n;
int st[maxn][20],log_2[maxn];
vector<int> to[maxn],c[maxn];
int f[maxn][20],dep[maxn];
void dfs(int x,int deep){
dep[x]=deep;
c[deep].push_back(x);
for(int y:to[x])if(y!=f[x][0]){
f[y][0]=x;
dfs(y,deep+1);
}
}
int get_lca(int x,int y){
if(dep[x]>dep[y])swap(x,y);
for(int j=17;j>=0;j--)
if(dep[f[y][j]]>=dep[x])
y=f[y][j];
if(x==y)return x;
for(int j=17;j>=0;j--)
if(f[x][j]!=f[y][j])
x=f[x][j],y=f[y][j];
return f[x][0];
}
struct DSU{
int fa[maxn];
void init(const int N){
for(int i=1;i<=N;i++)
fa[i]=i;
}
int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
void merge(int x,int y){
x=findfa(x); y=findfa(y);
if(x!=y)fa[x]=y;
}
}ds;
pair<int,int> g[maxn];
int main()
{
int Te;read(Te);while(Te--){
read(n);
for(int i=0;i<n;i++)
read(st[i][0]);
for(int i=1;i<=n;i++){
to[i].clear();
c[i].clear();
}
for(int i=1,x,y;i<n;i++){
read(x);read(y);
to[x].push_back(y);
to[y].push_back(x);
}
dfs(1,1);
for(int j=1;j<=17;j++)
for(int i=0;i<n-(1<<j)+1;i++)
st[i][j]=min(st[i][j-1], st[i+(1<<j-1)][j-1]);
for(int i=2;i<=n;i++)
log_2[i]=log_2[i>>1]+1;
auto query=[&](int x,int y){
if(x>y)return 1000000000;
int lg=log_2[y-x+1];
return min(st[x][lg], st[y-(1<<lg)+1][lg]);
};
for(int j=1;j<=17;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
ds.init(n);
for(int i=1;i<=n;i++)g[i]=make_pair(i,st[0][0]);
long long ans=0;
for(int i=1;i<=n;i++)if(c[i].size()){
vector<array<int,3>> d;
for(int j=0;j<c[i].size()-1;j++){
d.push_back({c[i][j], c[i][j+1], dep[get_lca(c[i][j],c[i][j+1])]});
}
sort(d.begin(),d.end(),[&](array<int,3> x,array<int,3> y){
return x[2]<y[2];
});
for(auto j:d){
int x=ds.findfa(j[0]), y=ds.findfa(j[1]);
int lca = get_lca(g[x].first,g[y].first);
// assert(dep[lca] == j[2]);
g[x].second = min(g[x].second, query(i-dep[g[x].first], i-dep[lca]));
g[y].second = min(g[y].second, query(i-dep[g[y].first], i-dep[lca]));
int z=g[x].second + g[y].second;
ds.fa[x]=y;
g[y] = make_pair(lca,z);
}
int dg = ds.findfa(c[i][0]);
g[dg].second = min(g[dg].second, query(i-dep[g[dg].first], i-dep[1]));
ans += g[dg].second;
}
write(ans);puts("");
}
}
/*
1
4
10 15 40 1
1 2
2 3
2 4
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11628kb
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: 36ms
memory: 11732kb
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:
185 177 222 230 156 255 225 126 100 81 171 73 159 157 160 152 228 230 140 200 155 171 78 282 195 286 204 211 119 215 211 252 88 252 239 244 175 180 195 145 109 149 180 188 226 210 182 97 252 59 56 31 115 224 203 172 155 217 53 158 189 187 173 137 233 106 163 273 80 350 156 133 172 159 252 269 157 22...
result:
wrong answer 1st numbers differ - expected: '180', found: '185'