QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#177212#5418. Color the TreebrzWA 36ms11732kbC++202.8kb2023-09-12 17:51:442023-09-12 17:51:44

Judging History

你现在查看的是最新测评结果

  • [2023-09-12 17:51:44]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:11732kb
  • [2023-09-12 17:51:44]
  • 提交

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'