oj.uz

Submission #824447

# Submission time Handle Problem Language Result Execution time Memory
824447 2023-08-14T06:27:46 Z 반딧불(#10358) Winter Driving (CCO19_day1problem3) C++17
0 / 25
 71 ms 10052 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll arr[200002];
int par[200002];
vector<int> link[200002];

ll sz[200002], bonus[200002];

void dfs(int x, int p){
	sz[x] = arr[x];
	bonus[x] = 0;
	for(auto y: link[x]){
		if(y==p) continue;
		dfs(y, x);
		sz[x] += sz[y];
		bonus[x] += bonus[y];
	}
	bonus[x] += (sz[x] - arr[x]) * arr[x];
}

ll ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    for(int i=2; i<=n; i++) scanf("%d", &par[i]), link[par[i]].push_back(i), link[i].push_back(par[i]);
    ll sum = accumulate(arr+1, arr+n+1, 0LL);
	ll base = 0;
	for(int i=1; i<=n; i++) base += arr[i] * (arr[i]-1);

	dfs(1, -1);

	vector<int> centroids;
	for(int i=1; i<=n; i++){
		bool good = 1;
		if(sz[i] < (sum+1)/2) continue;
		for(int j: link[i]){
			if(j==par[i]) continue;
			if(sz[j]*2 > sum) good = 0;
		}
		if(good) centroids.push_back(i);
	}

    for(int i: centroids){
    	dfs(i, -1);
    	vector<ll> v;
    	ll b = bonus[i];
    	for(int j: link[i]) v.push_back(sz[j]);

    	int S = (int)v.size();
    	if(S < 2){
	    	for(int d=0; d<(1<<(int)link[i].size()); d++){
	    		ll a = 0;
	    		for(int j=0; j<(int)link[i].size(); j++){
	    			if((d>>j)&1) a += v[j];
	    		}
	    		ans = max(ans, a * (sum-arr[i]-a) + b);
	    	}
	    }
	    else{
	    	ll total = sum - arr[i];
	    	int A = S/2, B = S-A;
	    	vector<ll> v1, v2;
	    	for(int d=0; d<(1<<A); d++){
	    		ll a = 0;
	    		for(int j=0; j<A; j++) if((d>>j)&1) a += v[j];
	    		v1.push_back(a);
	    	}
	    	for(int d=0; d<(1<<B); d++){
	    		ll a = 0;
	    		for(int j=0; j<B; j++) if((d>>j)&1) a += v[j+A];
	    		v2.push_back(a);
	    	}
	    	sort(v1.begin(), v1.end());
	    	sort(v2.begin(), v2.end());
	    	for(ll a: v1){
	    		ll y = total - a;
	    		auto it = lower_bound(v2.begin(), v2.end(), y);
	    		if(it != v2.end()) ans = max(ans, (a+*it) * (total-a-*it) + b);
	    		if(it != v2.begin()){
	    			--it;
	    			ans = max(ans, (a+*it) * (total-a-*it) + b);
	    		}
	    	}
	    }
    }
	printf("%lld", ans + base);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:30:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:31:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     for(int i=2; i<=n; i++) scanf("%d", &par[i]), link[par[i]].push_back(i), link[i].push_back(par[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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