Submission #251491

#	Time	Username	Problem	Language	Result	Execution time	Memory
251491		Vimmer	Zagrade (COI17_zagrade)	C++14	100 / 100	1525 ms	52236 KiB

zagrade

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define N 300010

using namespace std;

typedef long long ll;

map<int,int> mp;

vector <int> g[N];

int sz[N], n, bl[N], need[N], res[N];

ll ans = 0;

bool mk[N];

string s;

void dfs(int v, int p)
{
    sz[v] = 1;

    for (auto it : g[v])
    {
        if (it == p || mk[it]) continue;

        dfs(it, v);

        sz[v] += sz[it];
    }
}

int fnd_cent(int v, int p)
{
    if (p != -1) {sz[p] -= sz[v]; sz[v] += sz[p];}

    for (auto it : g[v])
        if (!mk[it] && sz[it] + sz[it] > sz[v]) return fnd_cent(it, v);

    return v;
}

void rec(int v, int p, bool f)
{
    if (need[v] == abs(bl[v]) && bl[v] <= 0 && res[v] == 0) mp[abs(bl[v])]++;

    if (!f && bl[v] == 0 && need[v] == 0 && res[v] == 0) ans++;

    for (auto it : g[v])
    {
        if (mk[it] || it == p) continue;

        if (!f)
        {
            bl[it] = bl[v];

            need[it] = need[v];

            res[it] = res[v];

            if (s[it] == '(') {res[it]++; bl[it]++;}
              else {bl[it]--; if (res[it] > 0) res[it]--; else need[it]++;}
        }

        rec(it, v, f);
    }
}

void dec(int v, int p)
{
    if (need[v] == abs(bl[v]) && bl[v] <= 0 && res[v] == 0) mp[abs(bl[v])]--;

    for (auto it : g[v])
    {
        if (mk[it] || it == p) continue;

        dec(it, v);
    }
}

void dfser(int v, int p, int need, int b)
{
    if (s[v] == '(') {b++; need--; need = max(need, 0);}
      else {need++; b--;}

    if (b >= 0 && need == 0) ans += ll(mp[b]);

    for (auto it : g[v])
    {
        if (mk[it] || it == p) continue;

        dfser(it, v, need, b);
    }
}
void calc(int v)
{
    mp.clear();

    mk[v] = 1;

    bl[v] = need[v] = res[v] = 0;

    if (s[v] == '(') {res[v]++; bl[v]++;}
      else {bl[v]--; need[v] = 1;}

    rec(v, -1, 0);

    for (auto it : g[v])
    {
        if (mk[it]) continue;

        dec(it, -1);

        dfser(it, -1, 0, 0);

        rec(it, -1, 1);
    }

    for (auto it : g[v])
    {
        if (mk[it]) continue;

        int root = fnd_cent(it, -1);

        if (root != -1)
        {
            dfs(root, -1);

            calc(root);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    cin >> s;

    for (int i = 1; i < n; i++)
    {
        int x, y;

        cin >> x >> y;

        x--; y--;

        g[x].pb(y);

        g[y].pb(x);
    }

    dfs(0, -1);

    int root = fnd_cent(0, -1);

    dfs(root, -1);

    calc(root);

    cout << ans << endl;
}

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