Submission #334575

#	Time	Username	Problem	Language	Result	Execution time	Memory
334575		Atill83	Zagrade (COI17_zagrade)	C++14	0 / 100	3087 ms	45912 KiB

zagrade

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
string s;
vector<int> adj[MAXN];
bool erased[MAXN];
int sz[MAXN];
ll ans = 0;
unordered_map<int, ll> mp;
void dfs(int v, int pr = -1){
    sz[v] = 1;
    for(int j: adj[v]){
        if(j != pr && !erased[j]){
            dfs(j, v);
            sz[v] += sz[j];
        }
    }
}

int cent(int v){
    int siz = sz[v];
    int pr = -1;
    bool cont = 1;
    while(cont){
        cont = 0;
        for(int j: adj[v]){
            if(erased[j] || j == pr) continue;
            if(2*sz[j] > siz){
                pr = v;
                v = j;
                cont = 1;
            }
        }
    }
    return v;

}

void upd(int v, int par, int val, int pre = 0, int tot = 0){
    if(s[v] == ')'){
        pre--;
        tot--;
    }else{
        pre++;
        tot = min(0, tot + 1);
    }

    //cerr<<v<<" "<<pre<<" "<<tot<<endl;
    if(tot == 0 && pre >= 0){
        mp[pre] += val;
    }

    for(int j: adj[v]){
        if(j != par && !erased[j]){
            upd(j, v, val, pre, tot);
        }
    }
}

void add(int v, int par, int pre = 0, int tot = 0){
    if(s[v] == ')'){
        pre++;
        tot = max(0, tot - 1);
    }else{
        pre--;
        tot++;
    }

    if(tot == 0 && pre >= 0){
        ans += mp[pre];
    }

    for(int j: adj[v]){
        if(!erased[j] && j != par){
            add(j, v, pre, tot);
        }
    }
}




void do_it(int v){
    dfs(v);
    v = cent(v);
    mp.clear();
    //cerr<<v<<endl;
    upd(v, -1, 1);
    ans += mp[0];
    int pr, tt;
    if(s[v] == ')')
        pr = tt = -1;
    else{
        pr = 1;
        tt = 0;
    }

    for(int j: adj[v]){
        if(erased[j])
            continue;
        upd(j, v, -1, pr, tt);
        add(j, v);
        upd(j, v, 1, pr, tt);
    }


    erased[v] = 1;
    for(int j: adj[v])
        if(!erased[j])
            do_it(j);
}






int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n;
    cin>>s;
    s = '.' + s;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    do_it(1);


    cout<<ans<<endl;

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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