oj.uz

Submission #936149

# Submission time Handle Problem Language Result Execution time Memory
936149 2024-03-01T09:23:00 Z shoryu386 The Xana coup (BOI21_xanadu) C++17
0 / 100
 81 ms 24976 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MAX 100007
int n;
vector<int> adj[MAX];

int dp[MAX][2][2];
int active[MAX];

bool comp(pair<int, int> a, pair<int, int> b){
	return a.second - a.first < b.second - b.first;
}

void dfs(int x, int p){
	for (auto y : adj[x]){ if (y == p) continue;
		dfs(y, x);
	}
	
	//we want to find the min presses to make even, and min presses to make odd
	if (true){
		vector<pair<int, int>> competition;
		int cursum = 0;
		for (auto y : adj[x]){ if (y == p) continue;
			competition.push_back({dp[y][0][0], dp[y][1][0]});
			cursum += dp[y][0][0];
		}
		
		int evenbest = cursum, oddbest = INT_MAX;
		sort(competition.begin(), competition.end(), comp);
		
		bool cureven = true;
		for (auto y : competition){
			cureven = !cureven;
			cursum += y.second - y.first;
			
			if (cureven) evenbest = min(evenbest, cursum);
			else oddbest = min(oddbest, cursum);
		}
		
		if (active[x]){
			dp[x][0][0] = oddbest;
			dp[x][0][1] = INT_MAX;
		}
		else{
			dp[x][0][1] = evenbest;
			dp[x][0][0] = INT_MAX;
		}
	}
	if (true){
		vector<pair<int, int>> competition;
		int cursum = 0;
		for (auto y : adj[x]){ if (y == p) continue;
			competition.push_back({dp[y][0][1], dp[y][1][1]});
			cursum += dp[y][0][1];
		}
		
		int evenbest = cursum, oddbest = INT_MAX;
		sort(competition.begin(), competition.end(), comp);
		
		bool cureven = true;
		for (auto y : competition){
			cureven = !cureven;
			cursum += y.second - y.first;
			
			if (cureven) evenbest = min(evenbest, cursum);
			else oddbest = min(oddbest, cursum);
		}
		
		if (active[x]){
			dp[x][1][1] = evenbest + 1;
			dp[x][1][0] = INT_MAX;
		}
		else{
			dp[x][1][1] = INT_MAX;
			dp[x][1][0] = oddbest + 1;
		}
	}
	
	//cout << x << ' ' << dp[x][0] << ' ' << dp[x][1] << '\n';
}

main(){
	cin >> n;
	for (int x = 0; x < n-1; x++){
		int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a);
	}
	for (int x = 0; x < n; x++) cin >> active[x];
	
	dfs(0, -1);
	
	int res = min(dp[0][0][0], dp[0][1][0]);
	
	if (res >= INT_MAX) cout << "impossible";
	else cout << res;
	
}

Compilation message

xanadu.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main(){
      | ^~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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

Subtask #5
0 / 30.0

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