Submission #1141056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141056		SmuggingSpun	Power Plant (JOI20_power)	C++20	100 / 100	310 ms	29056 KiB

power

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
const int lim = 2e5 + 5;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
int n;
namespace sub1{
	void solve(){
		vector<vector<int>>g(n);
		for(int i = 1; i < n; i++){
			int u, v;
			cin >> u >> v;
			g[--u].emplace_back(--v);
			g[v].emplace_back(u);
		}
		string s;
		cin >> s;
		vector<int>h(n), parent(n);
		auto dfs = [&] (auto&& self, int s) -> void{
			for(int& d : g[s]){
				if(d != parent[s]){
					h[d] = h[parent[d] = s] + 1;
					self(self, d); 
				}
			}
		};
		dfs(dfs, h[0] = parent[0] = 0);
		int ans = 0;
		for(int mask = (1 << n) - 1; mask > 0; mask--){
			vector<int>vertex;
			bool flag = true;
			for(int i = 0; i < n; i++){
				if(1 << i & mask){
					if(s[i] == '0'){
						flag = false;
						break;
					}
					vertex.emplace_back(i);
				}
			}
			if(flag){
				vector<bool>color(n, true);
				int sum = 0;
				for(int& u : vertex){
					for(int& v : vertex){
						vector<int>path;
						int U = u, V = v;
						while(U != V){
							if(h[U] < h[V]){
								swap(U, V);
							}
							path.emplace_back(U = parent[U]);
						}
						for(int& i : path){
							if(i != u && i != v && s[i] == '1' && color[i]){
								color[i] = false;
								sum--;
							}
						}
					}
				}
				for(int& i : vertex){
					if(color[i]){
						sum++;
					}
				}
				maximize(ans, sum);
			}
		}
		cout << ans;
	}
}
namespace sub2{
	void solve(){
		vector<vector<int>>g(n);
		for(int i = 1; i < n; i++){
			int u, v;
			cin >> u >> v;
			g[--u].emplace_back(--v);
			g[v].emplace_back(u);
		}
		string s;
		cin >> s;
		for(char& c : s){
			c -= 48;
		}
		vector<int>dp(n);
		auto dfs = [&] (auto&& self, int u, int p) -> void{
			dp[u] = 0;
			for(int& v : g[u]){
				if(v != p){
					self(self, v, u); 
					dp[u] += max(int(s[v]), dp[v] - s[v]);
				}
			}
		};
		int ans = -1;
		for(int i = 0; i < n; i++){
			if(s[i] == 1){
				dfs(dfs, i, -1);
				for(int& j : g[i]){
					maximize(ans, max(int(s[j]), dp[j] - s[j]));
				}
			}
		}
		cout << ans + 1;
	}
}
namespace sub3{
	const int lim = 2e5 + 5;
	vector<int>g[lim];
	string s;
	int ans = -1, dp[lim];
	void dfs_1(int u, int p = -1){
		dp[u] = 0;
		for(int& v : g[u]){
			if(v != p){
				dfs_1(v, u);
				dp[u] += max(int(s[v]), dp[v] - s[v]);
			}
		}
	}
	void dfs_2(int u, int p = -1){
		if(s[u] == 1){
			for(int& v : g[u]){
				maximize(ans, max(int(s[v]), dp[v] - s[v]));
			}
		}
		for(int& v : g[u]){
			if(v != p){
				dp[u] -= max(int(s[v]), dp[v] - s[v]);
				if(p != -1){
					dp[u] += max(int(s[p]), dp[p] - s[p]);
				}
				dfs_2(v, u);
				dp[u] += max(int(s[v]), dp[v] - s[v]);
				if(p != -1){
					dp[u] -= max(int(s[p]), dp[p] - s[p]);
				}
			}
		}
	}
	void solve(){
		for(int i = 1; i < n; i++){
			int u, v;
			cin >> u >> v;
			g[--u].emplace_back(--v);
			g[v].emplace_back(u);
		}
		cin >> s;
		for(char& c : s){
			c -= 48;
		}
		dfs_1(0);
		dfs_2(0);
		cout << ans + 1;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	if(n <= 16){
		sub1::solve();
	}
	else if(n <= 2000){
		sub2::solve();
	}
	else{
		sub3::solve();
	}
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:166:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53