oj.uz

Submission #948210

# Submission time Handle Problem Language Result Execution time Memory
948210 2024-03-17T21:49:27 Z amirhoseinfar1385 Chase (CEOI17_chase) C++17
100 / 100
 2115 ms 58952 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,maxv=102;
long long vis[maxn],n,mv,all[maxn],sz[maxn],mainres;
struct hal{
	vector<long long>adj[maxn];
	vector<int>tof;
	void con(long long u,long long v){
		tof.push_back(v);
		adj[v].push_back(u);
	}
	long long res,tamam[maxv],fakeres[maxv],ezaf[maxv],dovom[maxv];
	void clear(){
		res=0;
		for(long long i=0;i<maxv;i++){
			tamam[i]=fakeres[i]=ezaf[i]=dovom[i]=0;
		}
		for(auto x:tof){
			adj[x].clear();
		}
		tof.clear();
	}
	void build(long long u,long long par=-1){
		long long suma=0;
		for(auto x:adj[u]){
			if(x==par){
				continue;
			}
			suma+=all[x];
		}
		for(long long i=1;i<=mv;i++){
			long long wt=0;
			if(par!=-1){
				wt=all[par];
			}
			res=max(res,suma+fakeres[i-1]+tamam[mv-i]+wt);
			if(par!=-1&&i>0){
				ezaf[i]=max(ezaf[i],dovom[i-1]+suma);
			}
		}
		long long hey[maxv],hey2[maxv];
		for(long long i=0;i<maxv;i++){
			hey[i]=fakeres[i];
			hey2[i]=dovom[i];
		}
		for(auto x:adj[u]){
			if(x==par){
				continue;
			}
			long long wt=0;
			if(par!=-1){
				wt=all[par];
			}
			for(long long i=mv;i>=1;i--){
				fakeres[i]=max(fakeres[i],fakeres[i-1]+suma-all[x]+wt);
				if(par!=-1)
					dovom[i]=max(dovom[i],dovom[i-1]+suma);
			}
			build(x,u);
			for(long long i=0;i<maxv;i++){
				fakeres[i]=hey[i];
				dovom[i]=hey2[i];
			}
			if(par==-1){
				for(long long i=0;i<=mv;i++){
					tamam[i]=max(tamam[i],ezaf[i]);
					ezaf[i]=0;
				}
			}
		}
	}
}ds;

vector<long long>adj[maxn];

void vorod(){
	cin>>n>>mv;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

void calsz(long long u,long long par=-1){
	sz[u]=1;
	for(auto x:adj[u]){
		if(vis[x]||x==par){
			continue;
		}
		calsz(x,u);
		sz[u]+=sz[x];
	}
}

long long findcent(long long u,long long s,long long par=-1){
	for(auto x:adj[u]){
		if(x!=par&&vis[x]==0&&sz[x]*2>s){
			return findcent(x,s,u);
		}
	}
	return u;
}

void pass(long long u,long long par=-1){
	for(auto x:adj[u]){
		if(vis[x]==0&&x!=par){
			ds.con(x,u);
			pass(x,u);
		}
	}
}

void cal(long long u){
	ds.clear();
	pass(u);
	ds.build(u);
	mainres=max(mainres,ds.res);
	ds.clear();
	pass(u);
	reverse(ds.adj[u].begin(),ds.adj[u].end());
	ds.build(u);
	mainres=max(mainres,ds.res);
}

void solve(long long u=1){
	calsz(u);
	long long v=findcent(u,sz[u]);
	cal(v);
	vis[v]=1;
	for(auto x:adj[v]){
		if(vis[x]==0){
			solve(x);
		}
	}
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
//	if(n<=1000){
		solve();
//	}else{
//		cal(1);
//	}
	khor();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 14 ms 7260 KB Output is correct
8 Correct 5 ms 7260 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 8 ms 6748 KB Output is correct
11 Correct 5 ms 6748 KB Output is correct
12 Correct 4 ms 7000 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2115 ms 56628 KB Output is correct
2 Correct 2099 ms 58952 KB Output is correct
3 Correct 232 ms 15552 KB Output is correct
4 Correct 447 ms 15792 KB Output is correct
5 Correct 1191 ms 15820 KB Output is correct
6 Correct 1277 ms 16204 KB Output is correct
7 Correct 1214 ms 16168 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 14 ms 7260 KB Output is correct
8 Correct 5 ms 7260 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 8 ms 6748 KB Output is correct
11 Correct 5 ms 6748 KB Output is correct
12 Correct 4 ms 7000 KB Output is correct
13 Correct 2115 ms 56628 KB Output is correct
14 Correct 2099 ms 58952 KB Output is correct
15 Correct 232 ms 15552 KB Output is correct
16 Correct 447 ms 15792 KB Output is correct
17 Correct 1191 ms 15820 KB Output is correct
18 Correct 1277 ms 16204 KB Output is correct
19 Correct 1214 ms 16168 KB Output is correct
20 Correct 1169 ms 15720 KB Output is correct
21 Correct 320 ms 16076 KB Output is correct
22 Correct 1209 ms 16012 KB Output is correct
23 Correct 410 ms 15820 KB Output is correct
24 Correct 1167 ms 15988 KB Output is correct
25 Correct 240 ms 15184 KB Output is correct
26 Correct 2044 ms 58812 KB Output is correct
27 Correct 2081 ms 58812 KB Output is correct