oj.uz

답안 #763034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763034 2023-06-22T02:33:45 Z vjudge1 Power Plant (JOI20_power) C++17
0 / 100
 3 ms 4948 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef stack<ll> sll;
typedef queue<ll> qll;
typedef deque<ll> dll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
 
#define endl '\n'
#define pb push_back
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define BACK(i,a,b) for(int i = a; i >= b; i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define bp __builtin_popcountll
#define gcd __gcd
#define bit(i,n) ((n>>i)&1)
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
 
const int MAXN = (2e5)+5;
// const ll SQRT = 4;
const long long inf = 1e18;
const long long MOD = 998244353;

vector<int> adj[MAXN];
int n,f[MAXN],ans,par[MAXN],cnt[MAXN];
bool gen[MAXN];

int dp(int u)
{
	if(f[u]!=INT_MAX) return f[u];
	int res=cnt[u]-gen[u];
	for(auto v:adj[u]) if(v!=par[u]) if(dp(v)-gen[u]-gen[v]>0) res+=dp(v)-gen[u]-gen[v];
	return f[u]=res;
}

void dfs(int u)
{
	for(auto v:adj[u]) if(v!=par[u])
	{
		par[v]=u;
		dfs(v);
	}
}

signed main()
{
	fastIO
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	cin>>n;
	FOR(i,1,n-1)
	{
		int u,v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	FOR(i,1,n)
	{
		char c;
		cin>>c;
		gen[i]=(c=='1');
	}
	dfs(1);
	FOR(i,1,n) f[i]=INT_MAX;
	FOR(i,1,n) for(auto a:adj[i]) cnt[i]+=gen[a];
	FOR(i,1,n) ans=max(ans,dp(i));
	cout<<ans;
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -