QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212605#5418. Color the TreehazeWA 162ms3768kbC++204.1kb2023-10-13 18:07:372023-10-13 18:07:37

Judging History

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

  • [2023-10-13 18:07:37]
  • 评测
  • 测评结果:WA
  • 用时:162ms
  • 内存:3768kb
  • [2023-10-13 18:07:37]
  • 提交

answer

#include<bits/stdc++.h>
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,r,l) for(int i = r; i >= l; --i)
#define ceil(pp,qq) (((pp)>0)^((qq)>0)?-Abs(pp)/Abs(qq):(pp)%(qq)?(pp)/(qq)+1:(pp)/(qq))
#define floor(pp,qq) (((pp)>0)^((qq)>0)?-ceil(Abs(pp),Abs(qq)):(pp)/(qq))
#define ll long long
#define LL __int128
using namespace std;
ll Abs(ll x){return x > 0 ? x : - x;}
inline ll read(){
	char ch = getchar();
	ll s = 0; bool w = 0;
	while(!isdigit(ch)){if(ch == '-')w = 1;ch = getchar();}
	while(isdigit(ch))s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
	return w ? - s : s;
}

const int itinf = 1e9;
const ll llinf = 4e18;
const int mod = 1000000007;
const int N = 500009;

inline int mul(int nma, int nmb){
	return ((1ll * nma * nmb % mod) + mod) % mod;
}

void solve(){
	int n = read(), lst = 0;
	ll ans = 0;
	vector<ll>c(n), dp(n), dfn(n);
	vector<vector<int>>g(n), dset(n);
	vector<array<int, 24>>fa(n), minc(n);
	irep(i,0,n - 1)c[i] = minc[i][0] = read();
	irep(i,1,n - 1){
		int u = read() - 1, v = read() - 1;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	auto dfs = [&](auto self, int x) -> void{
//		cerr << x << ' ' << endl;
		dfn[x] = lst ++;
		dset[dp[x]].push_back(x);
		for(int y : g[x]){
			if(y != 0 && dp[y] == 0){
				dp[y] = dp[x] + 1;
				fa[y][0] = x;
				self(self, y);
			}
		}
	};
		
	dfs(dfs, 0);
//	cerr << fa[3][0];
	for(int r = 1; r <= 23; ++ r){
		for(int i = 0; i < n; ++ i){
			fa[i][r] = fa[fa[i][r - 1]][r - 1];
			if((i + (1 << (r - 1))) > n)minc[i][r] = minc[i][r - 1];
			else minc[i][r] = min(minc[i][r - 1], minc[i + (1 << (r - 1))][r - 1]);
		}
	}
	
	auto rmq = [&](int l, int r) -> int{
		if(l > r)swap(l, r);
		int len = r - l + 1, pw = __lg(len);
		return min(minc[l][pw], minc[r - (1 << pw) + 1][pw]);
	};
	
	auto lca = [&](int x, int y) -> int{
		if(x == y)return x;
		if(dp[x] < dp[y])swap(x, y);
		for(int r = 23; r >= 0; -- r){
			if(dp[fa[x][r]] >= dp[y])x = fa[x][r];
		}
		if(x == y)return x;
		for(int r = 23; r >= 0; -- r){
			if(fa[x][r] != fa[y][r]){
				x = fa[x][r] , y = fa[y][r];
			}
		}
		return fa[x][0];
	};
	for(int i = 1; i < n; ++ i){
		if(dset[i].size()){
			dset[i].push_back(0);
			sort(dset[i].begin(), dset[i].end(), [&](int x,int y){return dfn[x] < dfn[y];});
		}
		else break;
		
		int sz = dset[i].size();
		for(int j = 0; j + 1 < sz; ++ j){
			dset[i].push_back(lca(dset[i][j], dset[i][j + 1]));
		}
		
		sort(dset[i].begin(), dset[i].end(), [&](int x,int y){return dfn[x] < dfn[y];});
		dset[i].erase(unique(dset[i].begin(), dset[i].end()), dset[i].end());

	//	cerr << "PRINT dset\n";
	//	for(int hh : dset[i])cerr << hh << ' ';
	//	cerr << endl;		

		vector<array<int, 2>>edge;
		vector<vector<int>>tree;
		sz = dset[i].size();
		map<int,int> idx, fd;

		for(int j = 0; j + 1 < sz; ++ j){
			int lc = lca(dset[i][j], dset[i][j + 1]);
			edge.push_back({lc, dset[i][j + 1]});
			if(idx.find(lc) == idx.end())
				idx[lc] = idx.size(), fd[idx[lc]] = dp[lc];
			if(idx.find(dset[i][j + 1]) == idx.end())
				idx[dset[i][j + 1]] = idx.size(),
				fd[idx[dset[i][j + 1]]] = dp[dset[i][j + 1]];
		}

		tree.resize(idx.size());

		for(auto [x, y] : edge){
			int u = idx[x], v = idx[y];
			tree[u].push_back(v);
			tree[v].push_back(u);
		//	cerr << u << ' ' << v << endl;
		}
	//	cerr << endl;
		vector<ll>f(idx.size(), llinf);
		auto work = [&](auto self, int x, int fax) -> void{
			/*
				i -> depth
				cost = a[depth - dp[u]] or sum f[v]
				i - (fd[u])
				i - (fd[fax] + 1)
			*/
			f[x] = rmq(i - fd[fax] - 1, i - fd[x]);
			if(i == fd[x]){
				f[x] = c[i - fd[x]];
				return;
			}

			ll alt = 0;
			for(int y : tree[x]){
				if(fd[y] > fd[x]){
					self(self, y, x);
					alt += f[y];
				}
			}
		//	cout << "Dt " << i - fd[x] <<  ' ' << f[x] << ' ' << alt << endl;;
			f[x] = min(f[x], alt);
			
			
		};
		work(work, 0, 0);
		ans += f[0];
	//	cout << "F= " << f[0] << endl;
	//	cout << endl;
	}
	//cout << endl;
	printf("%lld\n", ans + c[0]);
}

int main(){
	int T = read();
	while(T --){
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3740kb

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: 162ms
memory: 3768kb

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:

146
116
191
208
153
225
211
134
100
85
180
82
157
135
172
117
198
198
137
179
138
126
78
218
190
245
156
176
88
159
157
210
71
247
212
195
176
172
174
116
96
116
180
163
221
183
155
133
149
59
56
22
127
183
186
122
155
194
50
105
155
136
161
123
205
87
152
219
80
362
150
116
129
147
197
231
107
177
...

result:

wrong answer 1st numbers differ - expected: '180', found: '146'