Submission #296125

#	Time	Username	Problem	Language	Result	Execution time	Memory
296125		maximath_1	Power Plant (JOI20_power)	C++11	0 / 100	9 ms	10496 KiB

power

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string.h>
#include <set>
#include <math.h>
#include <numeric>
#include <assert.h>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define endl "\n"
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> OST;
typedef tree<pair<int, int>, null_type, less_equal<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> OST_multiset;
const ll inf = 1e9 + 69;
const ld pi = 3.14159265358979323L;
const ld eps = 1e-15;
const int N = 1e5 + 5;

void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
	unsyncIO();
	if(s.size()){
		setIn(s + ".in");
		setOut(s + ".out");
	}
}

#define gc getchar//_unlocked
#define pc putchar//_unlocked
int inp(){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	int rs = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		rs = (rs << 1) + (rs << 3) + (c - '0');
	if(neg) rs = -rs;
	return rs;
}
void pri(int _n){
	int N = _n, rev, count = 0;
	rev = N;
	if(N == 0) {pc('0'); return;}
	while(rev % 10 == 0) {count ++; rev /= 10;}
	rev = 0;
	while(N != 0) {rev = (rev << 3) + (rev << 1) + N % 10; N /= 10;}
	while(rev != 0) {pc(rev % 10 + '0'); rev /= 10;}
	while(count --) pc('0');
}

int n;
vector<int> adj[200005];
bitset<200005> power; //powerhouse

vector<int> ct[200005]; //centroid tree
int remov[200005], sz[200005];

void subtree(int nw, int bf){
	sz[nw] = 1;
	for(int nx : adj[nw]) if(nx != bf && !remov[nx]){
		subtree(nx, nw);
		sz[nw] += sz[nx];
	}
}

int find_centroid(int nw){
	subtree(nw, -1);
	int tsz = sz[nw];
	for(bool found = 0; !found;){
		found = 1;
		for(int nx : adj[nw]) if(sz[nx] <= sz[nw] && !remov[nx]){
			if(sz[nx] >= tsz / 2){
				found = 0;
				nw = nx; break;
			}
		}
	}
	return nw;
}

int build_centroid_tree(int nw){
	nw = find_centroid(nw);
	remov[nw] = true;
	for(int nx : adj[nw]) if(!remov[nx]){
		nx = build_centroid_tree(nx);
		ct[nw].push_back(nx);
	}
	return nw;
}

ll dfs(int nw, int bf, int cnt_par){
	ll res;
	if(power[nw]) res = 1ll - cnt_par;
	else res = -100000000000000069ll;

	ll sm = 0, cnt = 0;
	for(int nx : adj[nw]) if(nx != bf && !remov[nx]){
		ll cr = dfs(nx, nw, cnt_par + power[nw]);
		if(cr < -1000000000000069ll) {cr = 0; cnt --;}
		sm += cr;
		cnt ++;
	}

	if(cnt > 0) sm += (cnt_par + power[nw]) * 1ll * (cnt - 1);
	else sm = -100000000000000069ll;

	return max(res, sm);
}

int eval(int rt){
	int res = dfs(rt, -1, 0);
	remov[rt] = 1;
	// for(int nx : ct[rt])
	// 	res = max(res, eval(nx));
	return res;
}

int main(){
	setIO();

	cin >> n;
	for(int u, v, i = 1; i < n; i ++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	string s; cin >> s;
	int count = 0;
	for(int i = 1; i <= n; i ++){
		if(s[i - 1] == '1'){
			power[i] = 1;
			count ++;
		}
	}

	if(count <= 2) {cout << count << endl; return 0;}

	int rt = find_centroid(1);
	memset(remov, 0, sizeof(remov));
	cout << max(eval(rt), 2) << endl;
	
	return 0;
}

Compilation message (stderr)

power.cpp: In function 'void setIn(std::string)':
power.cpp:30:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   30 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
power.cpp: In function 'void setOut(std::string)':
power.cpp:31:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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