Submission #673546

#	Time	Username	Problem	Language	Result	Execution time	Memory
673546		tar_palantir	Zagrade (COI17_zagrade)	C++17	100 / 100	709 ms	43312 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;

const int mn=3e5+11;

vector<int>adj[mn];
bool r[mn];// removed?
int sz[mn];

int get_tree_size(int u,int par=-1){
    sz[u]=1;
    for(int v:adj[u])if(v!=par && !r[v])
        sz[u]+=get_tree_size(v,u);
    return sz[u];
}
int get_centroid(int u,int tree_size,int par=-1){
    for(int v:adj[u])if(v!=par && !r[v])
        if(sz[v]*2>tree_size)
            return get_centroid(v,tree_size,u);
    return u;
}
// centroid helper functions

// data processing goes below
inline int get(char x){
    return x==')' ? -1 : 1;
}
char a[mn];

struct holder{
    int cnt[2*mn];
    int elements[3*mn],cc=0;

    inline void emplace(int x){
        elements[++cc]=x;
        cnt[x+mn]++;
    }
    inline void erase(int x){
        if(cnt[x+mn])cnt[x+mn]--;
    }
    inline int get(int x){
        return cnt[x+mn];
    }
    inline void clear(){
        while(cc)erase(elements[cc--]);
    }
}st;

void traverse(int u,int par,int cur,int dip,bool dir){
    if(dip>=0){
        if(dir)st.emplace(cur);
        else st.erase(cur);
    }
    for(int v:adj[u])if(v!=par && !r[v]){
        int nxt=cur+get(a[v]);
        traverse(v,u,nxt,min(dip+get(a[v]),get(a[v])),dir);
    }
}

long long res=0;
void dfs(int u,int par,int cur,int dip){
    if(-cur+dip>=0)res+=st.get(-cur);
    
    for(int v:adj[u])if(v!=par && !r[v]){
        int nxt=cur+get(a[v]);
        dfs(v,u,nxt,min(dip,nxt));
    }
}

void centroid_decompose(int root=1){
    root=get_centroid(root,get_tree_size(root));

    st.clear();
    traverse(root,-1,get(a[root]),get(a[root]),1);

    for(int other:adj[root])if(!r[other]){
        int cur=get(a[root])+get(a[other]);
        int dip=min(get(a[other]),cur);

        traverse(other,root,cur,dip,0);
        dfs(other,root,get(a[other]),get(a[other]));
        traverse(other,root,cur,dip,1);
    }
    res+=st.get(0);

    r[root]=true;
    for(int other:adj[root])if(!r[other])
        centroid_decompose(other);
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    #ifdef _TPR_
        freopen("t.inp","r",stdin);
        freopen("t.out","w",stdout);
    #endif
    int n;cin>>n;
    cin>>a+1;

    for(int i=2,u,v;i<=n;i++){
        cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    centroid_decompose();
    return cout<<res,0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int32_t main()':
zagrade.cpp:99:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     cin>>a+1;
      |          ~^~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60