Submission #1165309

#TimeUsernameProblemLanguageResultExecution timeMemory
1165309MPGPower Plant (JOI20_power)C++20
100 / 100
74 ms36796 KiB
//#pragma GCC optomize("Ofast") #pragma GCC optimize("unroll-loops") //#pragma GCC optimize("O3") //#pragma GCC target("avx2") //#pragma GCC target("sse,sse2,sse4.1,sse4.2") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define max_heap priority_queue<pair <ll, pair <ll, ll>>> #define min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> //#define min_heap priority_queue<ll, vector<ll>, greater<ll>> #define sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); #define filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); #define endl '\n' #define md(a) (a % mod + mod) % mod #define pb push_back //cout << vectorprecision(5) << fixed << f; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll const maxn = 2e5 + 123; ll const inf = 2e12; ll const loG = 23; ll const mod = 1e9 + 7; //ll const mod = 998244353; ll const sq = 350; ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;} ll n, dp[maxn][2], col[maxn]; vector <ll> g[maxn]; void dfs(ll v, ll p){ ll mx0 = 0, mx1 = 0, sum0 = 0, sum1 = 0; for (ll u : g[v]){ if (u != p){ dfs(u, v); mx0 = max(mx0, dp[u][0]); mx1 = max(mx1, dp[u][1]); sum0 += max((ll)0, dp[u][0]); sum1 += max((ll)0, dp[u][1]); } } //cout << v << ' ' << col[v] << ' ' << sum0 << ' ' << mx1 << endl; if (col[v]){ dp[v][0] = max(max(mx1 + 1, mx0), max((ll)1, sum1 - 1)); //dp[v][0] = max({(ll)1, sum0 - 1, mx1 + 1}); dp[v][1] = max((ll)1, sum1 - 1); } else{ dp[v][0] = max(sum1, mx0); dp[v][1] = sum1; } } string s; void Solve(){ cin >> n; for (int i = 1; i < n; i++){ ll a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } cin >> s; s = ' ' + s; for (int i = 1; i < n + 1; i++){ if (s[i] == '1') col[i] = 1; } dfs(1, 1); // for (int i = 1; i < n + 1; i++){ // cout << i << ' ' << col[i] << ' ' << dp[i][0] << ' ' << dp[i][1] << endl; // } cout << dp[1][0] << endl; } int main(){ sariE;// filE; int test = 1; //cin >> test; while (test--) Solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...