제출 #1304218

#제출 시각아이디문제언어결과실행 시간메모리
1304218hoa208Power Plant (JOI20_power)C++20
0 / 100
2 ms576 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
//--------------------------------------------------------------------

const ll N = 2e5 + 10;
ll n;
vector<ll> g[N];
ll h[N], up[N][20];
ll f[N], c[N];
ll in[N], en[N], m, sz[N], arr[N];
void dfs(ll u, ll p) {
	f[u] += c[u];
	in[u] = ++m;
	arr[m] = u;
	sz[u] = c[u];
	for(auto v : g[u]) {
		if(v == p) continue;
		h[v] = h[u] + 1;
		f[v] = f[u];
		up[v][0] = u;
		FOR(i, 1, 18) {
			up[v][i] = up[up[v][i - 1]][i - 1];
		}
		dfs(v, u);
		sz[u] += sz[v];
	}
	en[u] = m;
}
ll get(ll u, ll k) {
	for(int j = 0; (1 << j) <= k; j++) {
		if(bit(k, j)) u = up[u][j];
	}
	return u;
}
ll lca(ll u, ll v) {
	if(h[u] < h[v]) swap(u, v);
	u = get(u, h[u] - h[v]);
	if(v == u) return u;
	FORD(i, 18, 0) {
		if(up[u][i] != up[v][i]) {
			u = up[u][i];
			v = up[v][i];
		}
	}
	return up[u][0];
}
ll dist(ll u, ll v) {
	ll p = lca(u, v);
	return f[u] - f[v] + 2 * f[p] + c[p];
}
bool dx[N];
void dfs2(ll u, ll p, ll &cur) {
	if(dx[u]) return;
	cur += c[u];
	for(auto v : g[u]) {
		if(v == p) continue;
		dfs2(v, u, cur);
	}
}
void hbmt() {
	cin >> n;
	FOR(i, 1, n - 1) {
		ll u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	ll cnt = 0;
	FOR(i, 1, n) {
		char x;
		cin >> x;
		c[i] = x - '0';
		cnt += c[i];
	}
	ll ans = 0;
	ans = min(cnt, 2LL);
	if(cnt == 0) {
		cout << 0;
		return;
	}
	dfs(1, 0);
	vector<ll> vt;
	FOR(i, 1, n) {
		ll u = arr[i];
		if(c[u] == 1 && sz[u] <= 2) {
			vt.push_back(u);
			i = en[u];
		}
	}
	sort(vt.begin(), vt.end(), [&] (ll &x, ll &y) {
		return in[x] < in[y];
	});
	ll p = vt[0];
	FOR(i, 1, vt.size() - 1) {
		ll u = vt[i];
		p = lca(p, u);
	}
	ll cur = sz[p];
	dx[p] = 1;
	FOR(i, 0, vt.size() - 1) {
		ll u = vt[i];
		cur -= sz[u];
	}
	ll sz = vt.size();
	cur = sz - cur;
	dfs2(1, 0, cur);
	cout << max(ans, cur);
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	#define NAME "hbmt"
	if(fopen(NAME".inp", "r")) {
		freopen(NAME".inp", "r", stdin);
		freopen(NAME".out", "w", stdout);
	}
	
	//int t;cin>>t;while(t--)
	hbmt();
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

power.cpp: In function 'int main()':
power.cpp:126:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |                 freopen(NAME".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:127:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |                 freopen(NAME".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...