Submission #480605

#TimeUsernameProblemLanguageResultExecution timeMemory
480605MOUF_MAHMALATZagrade (COI17_zagrade)C++14
0 / 100
537 ms44816 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() #define F first #define S second using namespace std; typedef long long ll; ll n,c[300009],x,y,ans,sz[300009]; bool is[300009]; char cc; vector<vector<ll> >v; map<ll,ll>mp; void dfs(ll d,ll p) { sz[d]=1; for(auto z:v[d]) { if(z==p||is[z]) continue; dfs(z,d); sz[d]+=sz[z]; } } ll centroid(ll d,ll p,ll op) { for(auto z:v[d]) { if(z==p||is[z]) continue; if(sz[z]>op) return centroid(z,d,op); } return d; } void best(ll d,ll p,ll cur,ll mx,bool b) { cur+=c[d]; mx=max(mx,cur); if(cur>=mx) mp[cur]++; if(cur<0) b=0; if(mx==0&&cur==0) ans++; if(b&&cur==0) ans++; for(auto z:v[d]) { if(z==p||is[z]) continue; best(z,d,cur,mx,b); } } void rem(ll d,ll p,ll cur,ll mx) { cur+=c[d]; mx=max(mx,cur); if(cur>=mx) mp[cur]--; for(auto z:v[d]) { if(z==p||is[z]) continue; rem(z,d,cur,mx); } } void add(ll d,ll p,ll cur,ll mx) { cur+=c[d]; mx=max(mx,cur); if(cur>=mx) mp[cur]++; for(auto z:v[d]) { if(z==p||is[z]) continue; add(z,d,cur,mx); } } void op(ll d,ll p,ll cur,ll mn) { cur+=c[d]; mn=min(mn,cur); if(cur<=mn) ans+=mp[-cur]; for(auto z:v[d]) { if(z==p||is[z]) continue; op(z,d,cur,mn); } } void calc(ll o) { dfs(o,0); o=centroid(o,0,sz[o]/2); is[o]=1; mp.clear(); best(o,o,0,0,1); for(auto z:v[o]) { if(is[z]) continue; rem(z,z,c[o],max(0LL,c[o])); if(c[o]==1) mp[1]--; op(z,z,0,0); add(z,z,c[o],max(0LL,c[o])); if(c[o]==1) mp[o]++; } for(auto z:v[o]) if(!is[z]) calc(z); } int main() { ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; v.resize(n+1); for(ll i=1; i<=n; i++) { cin>>cc; if(cc=='(') c[i]=1; else c[i]=-1; } for(ll i=1; i<n; i++) { cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } calc(1); cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...