oj.uz

Submission #161911

# Submission time Handle Problem Language Result Execution time Memory
161911 2019-11-05T09:48:39 Z shayan_p Chase (CEOI17_chase) C++14
70 / 100
 683 ms 261240 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 );
    }
    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;
	}
    }
    ANS=max(ANS, dn[u][k]);
}
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);
    }
    if(n<=1000)
	for(int i=1;i<=n;i++)
	    dfsdn(i);
    else
	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 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 651 ms 4472 KB Output is correct
8 Correct 151 ms 4600 KB Output is correct
9 Correct 165 ms 4344 KB Output is correct
10 Correct 683 ms 4472 KB Output is correct
11 Correct 289 ms 4472 KB Output is correct
12 Correct 170 ms 4472 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 259520 KB Output is correct
2 Correct 537 ms 259588 KB Output is correct
3 Correct 411 ms 253688 KB Output is correct
4 Correct 382 ms 253084 KB Output is correct
5 Correct 578 ms 253052 KB Output is correct
6 Correct 605 ms 253176 KB Output is correct
7 Correct 590 ms 253176 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 651 ms 4472 KB Output is correct
8 Correct 151 ms 4600 KB Output is correct
9 Correct 165 ms 4344 KB Output is correct
10 Correct 683 ms 4472 KB Output is correct
11 Correct 289 ms 4472 KB Output is correct
12 Correct 170 ms 4472 KB Output is correct
13 Correct 544 ms 259520 KB Output is correct
14 Correct 537 ms 259588 KB Output is correct
15 Correct 411 ms 253688 KB Output is correct
16 Correct 382 ms 253084 KB Output is correct
17 Correct 578 ms 253052 KB Output is correct
18 Correct 605 ms 253176 KB Output is correct
19 Correct 590 ms 253176 KB Output is correct
20 Correct 592 ms 255016 KB Output is correct
21 Correct 357 ms 240888 KB Output is correct
22 Correct 590 ms 255036 KB Output is correct
23 Correct 463 ms 255092 KB Output is correct
24 Correct 576 ms 254920 KB Output is correct
25 Correct 409 ms 254960 KB Output is correct
26 Incorrect 542 ms 261240 KB Output isn't correct
27 Halted 0 ms 0 KB -