oj.uz

Submission #948207

# Submission time Handle Problem Language Result Execution time Memory
948207 2024-03-17T21:44:52 Z amirhoseinfar1385 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 56000 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];
	void con(long long u,long long 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(long long i=0;i<maxn;i++){
			adj[i].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++){
			int 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(int i=0;i<maxv;i++){
			hey[i]=fakeres[i];
			hey2[i]=dovom[i];
		}
		for(auto x:adj[u]){
			if(x==par){
				continue;
			}
			int 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(int 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]);
//	cout<<"st: "<<u<<" "<<v<<endl;
	cal(v);
//	cout<<"te: "<<u<<" "<<v<<endl;
	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();
	solve();
	khor();
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 140 ms 7260 KB Output is correct
8 Correct 133 ms 7260 KB Output is correct
9 Correct 131 ms 6844 KB Output is correct
10 Correct 160 ms 6992 KB Output is correct
11 Correct 130 ms 7076 KB Output is correct
12 Correct 132 ms 6744 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4045 ms 56000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 140 ms 7260 KB Output is correct
8 Correct 133 ms 7260 KB Output is correct
9 Correct 131 ms 6844 KB Output is correct
10 Correct 160 ms 6992 KB Output is correct
11 Correct 130 ms 7076 KB Output is correct
12 Correct 132 ms 6744 KB Output is correct
13 Execution timed out 4045 ms 56000 KB Time limit exceeded
14 Halted 0 ms 0 KB -