oj.uz

Submission #161927

# Submission time Handle Problem Language Result Execution time Memory
161927 2019-11-05T10:14:39 Z shayan_p Chase (CEOI17_chase) C++14
100 / 100
 605 ms 261204 KB 
// Remember...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10, maxk=105;
const ll inf=1e18;

vector<int> v[maxn];
int a[maxn], n, k;
ll dn[maxn][maxk], up[maxn][maxk], arr[maxk], ANS;
int who[maxn][maxk][2];

void dfsdn(int u,int par=-1){
    memset(dn[u],0,sizeof dn[u]);
    ll num=0;
    for(int y:v[u]){
	if(y==par) continue;
	num+= a[y];
    }
    for(int y:v[u]){
	if(y==par) continue;
	dfsdn(y,u);
	for(int i=0;i<=k;i++)
	    dn[u][i]= max( dn[u][i], dn[y][i] );
	for(int i=0;i< k;i++)
	    dn[u][i+1]= max( dn[u][i+1], dn[y][i] + num ), ANS=max(ANS, dn[y][i]+ num + (par==-1 ? 0 : a[par]) );
    }
    for(int i=0;i<=k;i++)
	who[u][i][0]= who[u][i][1]= -1;
    for(int y:v[u]){
	if(y==par) continue;
	for(int i=0;i<=k;i++){
	    if(who[u][i][0]==-1 || dn[y][i]>dn[ who[u][i][0] ][i])
		who[u][i][1]= who[u][i][0], who[u][i][0]=y;
	    else if(who[u][i][1]==-1 || dn[y][i]>dn[ who[u][i][1] ][i])
		who[u][i][1]=y;
	}
    }
}
void dfs(int u,int par=-1){
    ll num=0;
    for(int y:v[u])
	num+= a[y];
    for(int y:v[u]){
	if(y==par) continue;
	dfs(y,u);
	for(int i=0;i<=k;i++){
	    arr[i]= up[y][i];
	}
	for(int i=1;i<=k;i++){
	    arr[i]= max(arr[i], up[y][i-1] + num - a[y]);
	}
	for(int i=0;i<=k;i++){
	    int vert= who[u][k-i][0] == y ? who[u][k-i][1] : who[u][k-i][0];
	    ANS=max(ANS, arr[i] + dn[vert][k-i]);
	}
	for(int i=0;i<=k;i++){
	    up[u][i]= max(up[u][i], arr[i]);
	}
    }
    for(int i=1;i<=k;i++){
	up[u][i]= max(up[u][i], num);
    }
    ANS=max(ANS, up[u][k]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
		  
    cin>>n>>k;

    for(int i=1;i<=n;i++){
	cin>>a[i];
    }
    for(int i=0;i<n-1;i++){
	int a,b; cin>>a>>b;
	v[a].PB(b);
	v[b].PB(a);
    }
    dfsdn(1), dfs(1);
    return cout<<ANS<<endl,0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct
7 Correct 9 ms 5240 KB Output is correct
8 Correct 7 ms 5240 KB Output is correct
9 Correct 7 ms 5240 KB Output is correct
10 Correct 7 ms 5368 KB Output is correct
11 Correct 7 ms 5240 KB Output is correct
12 Correct 7 ms 5240 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 259704 KB Output is correct
2 Correct 545 ms 260084 KB Output is correct
3 Correct 422 ms 254408 KB Output is correct
4 Correct 380 ms 253872 KB Output is correct
5 Correct 605 ms 253972 KB Output is correct
6 Correct 581 ms 253944 KB Output is correct
7 Correct 587 ms 253940 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct
7 Correct 9 ms 5240 KB Output is correct
8 Correct 7 ms 5240 KB Output is correct
9 Correct 7 ms 5240 KB Output is correct
10 Correct 7 ms 5368 KB Output is correct
11 Correct 7 ms 5240 KB Output is correct
12 Correct 7 ms 5240 KB Output is correct
13 Correct 537 ms 259704 KB Output is correct
14 Correct 545 ms 260084 KB Output is correct
15 Correct 422 ms 254408 KB Output is correct
16 Correct 380 ms 253872 KB Output is correct
17 Correct 605 ms 253972 KB Output is correct
18 Correct 581 ms 253944 KB Output is correct
19 Correct 587 ms 253940 KB Output is correct
20 Correct 595 ms 254528 KB Output is correct
21 Correct 523 ms 240760 KB Output is correct
22 Correct 596 ms 254712 KB Output is correct
23 Correct 369 ms 254708 KB Output is correct
24 Correct 600 ms 254544 KB Output is correct
25 Correct 431 ms 254976 KB Output is correct
26 Correct 532 ms 260732 KB Output is correct
27 Correct 588 ms 261204 KB Output is correct