QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212810#5418. Color the TreehazeWA 155ms3772kbC++204.1kb2023-10-13 20:45:192023-10-13 20:45:19

Judging History

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

  • [2023-10-13 20:45:19]
  • 评测
  • 测评结果:WA
  • 用时:155ms
  • 内存:3772kb
  • [2023-10-13 20:45:19]
  • 提交

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) -> ll{
swap(l, r);
		if(l > r)return llinf;
//		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[x], i - fd[fax] - 1);
			if(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: 0ms
memory: 3672kb

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: 155ms
memory: 3772kb

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:

-6446744073709551448
-8893488147419103074
191
208
-2446744073709551462
-2446744073709551312
-6446744073709551398
139
114
87
182
83
-2446744073709551374
-6446744073709551438
5553255926290448594
-8893488147419103043
221
-6446744073709551452
-2446744073709551319
241
138
126
80
-2446744073709551234
221
...

result:

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