oj.uz

Submission #948208

# Submission time Handle Problem Language Result Execution time Memory
948208 2024-03-17T21:45:56 Z amirhoseinfar1385 Chase (CEOI17_chase) C++17
40 / 100
 249 ms 97212 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]);
	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 4 ms 6748 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6792 KB Output is correct
5 Correct 4 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 4 ms 6748 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6792 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 201 ms 7260 KB Output is correct
8 Correct 249 ms 7264 KB Output is correct
9 Correct 190 ms 6744 KB Output is correct
10 Correct 205 ms 6840 KB Output is correct
11 Correct 205 ms 6844 KB Output is correct
12 Correct 188 ms 6848 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6748 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6792 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 201 ms 7260 KB Output is correct
8 Correct 249 ms 7264 KB Output is correct
9 Correct 190 ms 6744 KB Output is correct
10 Correct 205 ms 6840 KB Output is correct
11 Correct 205 ms 6844 KB Output is correct
12 Correct 188 ms 6848 KB Output is correct
13 Incorrect 232 ms 97212 KB Output isn't correct
14 Halted 0 ms 0 KB -