Submission #80639

#	Time	Username	Problem	Language	Result	Execution time	Memory
80639		Hassoony	Zagrade (COI17_zagrade)	C++11	0 / 100	777 ms	46324 KiB

zagrade

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef double D;
const ll mod=1e9+7;
const ll inf=(1ll<<61);
const int MX=3e5+9;
int n,x,y,sub[MX],blocked[MX],par[MX];
vector<int>v[MX];
ll ans=0;
string s;
vector<int>nodes,f;
unordered_map<int,int>cnt;
void dfsbuild(int x,int p){
    sub[x]=1;
    par[x]=p;
    for(auto pp:v[x]){
        if(pp==p||blocked[pp])continue;
        dfsbuild(pp,x);
        sub[x]+=sub[pp];
    }
}
void dfs(int x,int p,int sum){
    nodes.push_back(sum);
    f.push_back(sum);
    for(auto pp:v[x]){
//            cout<<pp<<" "<<blocked[pp]<<endl;
        if(pp==p||blocked[pp])continue;
        if(s[pp]=='(')dfs(pp,x,sum+1);
        else dfs(pp,x,sum-1);
//        dfs(pp,x,sum+((s[pp]=='(')?1:-1));
    }
}
void create(int x){
    dfsbuild(x,-1);
    int S=sub[x],ind=-1;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int y=q.front();q.pop();
        int s=sub[x]-sub[y];
//        cout<<y<<" "<<s<<endl;
        for(auto pp:v[y]){
            if(pp==par[y]||blocked[pp])continue;
            s=max(s,sub[pp]);
//            cout<<s<<endl;
            q.push(pp);
        }
        if(S>s){
            S=s;
            ind=y;
        }
    }
//    cout<<ind<<endl;
    blocked[ind]=1;
    for(auto pp:f)cnt[pp]=0;
    f.clear();
    for(auto pp:v[ind]){
        if(blocked[pp])continue;
//        cout<<pp<<endl;
        if(s[pp]=='(')dfs(pp,ind,1);
        else dfs(pp,ind,-1);
//        dfs(pp,ind,(s[pp]=='(')?1:-1);
        for(auto pp:nodes){
//            cout<<pp<<endl;
            if(s[ind]=='(')pp++;
            else pp--;
            if(pp==0)ans++;
//            cout<<pp<<endl;
//            pp+=(s[ind]=='(')?1:-1;
            ans+=cnt[-pp];
        }
//        puts("");
        for(auto pp:nodes){
//            cout<<pp<<endl;
            cnt[pp]++;
        }
//        puts("");
        nodes.clear();
    }
    for(auto pp:v[ind]){
        if(blocked[pp])continue;
        create(pp);
    }
}
int main(){
    cin>>n>>s;
    s="#"+s;
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    create(1);
    cout<<ans<<endl;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~

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