Submission #293621

#TimeUsernameProblemLanguageResultExecution timeMemory
293621errorgornPower Plant (JOI20_power)C++14
100 / 100
1252 ms75576 KiB
//雪花飄飄北風嘯嘯 //天地一片蒼茫 #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; #define ll long long #define ii pair<ll,ll> #define iii pair<ii,ll> #define fi first #define se second #define endl '\n' #define debug(x) cout << #x << " is " << x << endl #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> //change less to less_equal for non distinct pbds, but erase will bug mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int n; vector<int> al[200005]; string s; map<ii,int> memo; int par[200005]; int val[200005]; int dfs(int i,int p){ if (memo.count(ii(i,p))) return memo[ii(i,p)]; int res=0; if (par[i]==-2){ for (auto &it:al[i]){ if (it==p) continue; res+=dfs(it,i); } par[i]=p; val[i]=res; } else{ res=val[i]; if (par[i]!=-1) res+=dfs(par[i],i); if (p!=-1) res-=dfs(p,i); } res+=(s[i]=='1'?-1:0); return memo[ii(i,p)]=max(res,(s[i]=='1'?1:0)); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin>>n; rep(x,0,n) par[x]=-2; int a,b; rep(x,1,n){ cin>>a>>b; a--,b--; al[a].push_back(b); al[b].push_back(a); } cin>>s; int ans=0; rep(x,0,n) if (s[x]=='1') ans++; ans=min(ans,2); rep(x,0,n){ ans=max(dfs(x,-1),ans); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...