Submission #1308850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308850		vili	Zagrade (COI17_zagrade)	C++20	0 / 100	394 ms	38532 KiB

zagrade

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

#define LL long long
#define int LL
#define PB push_back

const int N = 6e5 + 5;

vector<int> v[N];
int sz[N];
bool flg[N];
string s;
int put[N];
long long rj = 0;

vector<int> touched;

int zbroji(char a) {
    return (a == '(' ? 1 : -1);
}

void dfs(int tr, int pr = -1) {
    sz[tr] = 1;
    for (int nx : v[tr]) {
        if (nx == pr || flg[nx]) continue;
        dfs(nx, tr);
        sz[tr] += sz[nx];
    }
}

int fnd_cnt(int tr, int n, int pr = -1) {
    for (int nx : v[tr]) {
        if (nx == pr || flg[nx]) continue;
        if (sz[nx] * 2 > n)
            return fnd_cnt(nx, n, tr);
    }
    return tr;
}

void umi(int tr, int pr, bool cnt, int br, int brm, int md) {
    br += zbroji(s[tr]);
    brm += zbroji(s[tr]);
    brm = min(0LL, brm);
    md = min(md, br);

    if (cnt) {
        if (br <= 0 && br == md) {
            if (-br < N) rj += put[-br];
        }
    } else {
        if (brm >= 0 && br >= 0) {
            if (put[br] == 0) touched.PB(br);
            put[br]++;
        }
    }

    for (int nx : v[tr]) {
        if (nx == pr || flg[nx]) continue;
        umi(nx, tr, cnt, br, brm, md);
    }
}

void clear_put() {
    for (int x : touched) put[x] = 0;
    touched.clear();
}

void cnt(int tr) {
    dfs(tr);
    int c = fnd_cnt(tr, sz[tr]);
    flg[c] = true;

    int delta = zbroji(s[c]);
    put[0] = 1;
    touched.PB(0);

    for (int nx : v[c]) {
        if (flg[nx]) continue;
        umi(nx, c, true, delta, delta, delta);
        umi(nx, c, false, 0, 0, 0);
    }

    if (delta < 0 && -delta < N) rj += put[-delta];

    clear_put();

    reverse(v[c].begin(), v[c].end());

    put[0] = 1;
    touched.PB(0);

    for (int nx : v[c]) {
        if (flg[nx]) continue;
        umi(nx, c, true, delta, delta, delta);
        umi(nx, c, false, 0, 0, 0);
    }

    clear_put();

    for (int nx : v[c]) {
        if (!flg[nx]) cnt(nx);
    }
}

void solve() {
    int n;
    cin >> n;
    cin >> s;
    s = ' ' + s;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        v[a].PB(b);
        v[b].PB(a);
    }

    cnt(1);
    cout << rj << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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