Submission #428165

#TimeUsernameProblemLanguageResultExecution timeMemory
428165cfalasPower Plant (JOI20_power)C++14
0 / 100
1 ms204 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000007 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<ll, ll> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto v : a) int t, n; vi a, b; vector<vi> adj; int ans=0; string x; int cnt[300000]; int dfsc(int s, int p=-1){ cnt[s] = (x[s-1]=='1'); FOA(v,adj[s]) if(v!=p) cnt[s] += dfsc(v,s); return cnt[s]; } int dp[300000]; int dfs(int s, int p=-1){ if(dp[s]!=-1) return dp[s]; int ans2=0; vi b; //ans2 = max(ans2, min(2, cnt[s])); if(x[s-1]=='1') ans2 = 1; int ans3 = 0; if(x[s-1]=='1') ans3--; FOA(v, adj[s]){ if(v==p) continue; //cout<<s<<" going to "<<v<<endl; ans3 += dfs(v,s); if(cnt[1]==cnt[s] && x[s-1]=='1') ans2 = max(ans2, 1+dfs(v,s)); } ans2 = max(ans2, ans3); //cout<<s<<" "<<prev<<" "<<ans2<<" "<<ans3<<endl; dp[s] = ans2; return ans2; } int main(){ cin>>n; adj.assign(n+1, vi()); FOR(i,n+1) dp[i] = -1; FOR(i,n-1){ int a, b; cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a); } cin>>x; dfsc(1); cout<<max(min(2, cnt[1]),dfs(1))<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...