QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#177210 | #5418. Color the Tree | brz | RE | 0ms | 13772kb | C++20 | 2.8kb | 2023-09-12 17:50:27 | 2023-09-12 17:50:27 |
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13772kb
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
Runtime Error
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...