oj.uz

Submission #948209

# Submission time Handle Problem Language Result Execution time Memory
948209 2024-03-17T21:47:07 Z amirhoseinfar1385 Chase (CEOI17_chase) C++17
40 / 100
 219 ms 97116 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++){
			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 3 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 4 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 3 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 4 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 209 ms 7260 KB Output is correct
8 Correct 195 ms 7260 KB Output is correct
9 Correct 186 ms 6832 KB Output is correct
10 Correct 201 ms 6748 KB Output is correct
11 Correct 199 ms 6748 KB Output is correct
12 Correct 190 ms 6852 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 97116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 4 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 209 ms 7260 KB Output is correct
8 Correct 195 ms 7260 KB Output is correct
9 Correct 186 ms 6832 KB Output is correct
10 Correct 201 ms 6748 KB Output is correct
11 Correct 199 ms 6748 KB Output is correct
12 Correct 190 ms 6852 KB Output is correct
13 Incorrect 219 ms 97116 KB Output isn't correct
14 Halted 0 ms 0 KB -