Submission #1308733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308733		gkos5678	Zagrade (COI17_zagrade)	C++20	100 / 100	572 ms	57332 KiB

zagrade

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

#define pb push_back
#define all(v) v.begin(), v.end()

typedef long long ll;
typedef vector<int> vi;

const int maxn = 3e5 + 7;

ll n, c, it, val[maxn], sz[maxn], d[maxn], mf[maxn], mb[maxn], cnt[2 * maxn];
ll add, ans;
bool vis[maxn];
string s;
vi g[maxn];

void dfs1(int v, int p){
    sz[v] = 1;
    d[v] = d[p] + val[v];
    mb[v] = min(0LL, val[v] + mb[p]);
    mf[v] = min(mf[p], d[v] - val[c]);
    for (int ne : g[v]){
        if (vis[ne] || ne == p)
            continue;
        dfs1(ne, v);
        sz[v] += sz[ne];
    }
}

int cen(int v, int p){
    bool b = 1;
    for (int ne : g[v]){
        if (vis[ne])
            continue;
        if (sz[ne] > sz[v] / 2)
            b = 0;
    }
    if (b)
        return v;
    for (int ch : g[v]){
        if (ch == p || vis[ch])
            continue;
        sz[v] -= sz[ch];
        sz[ch] += sz[v];
        int ret = cen(ch, v);
        if (ret != -1)
            return ret;
        sz[ch] -= sz[v];
        sz[v] += sz[ch];
    }
    return -1;
}

void dfs2(int v, int p, bool b){
    int db = d[v] - val[c];
    if (b){
        add += (mf[v] >= db) * cnt[sz[c] - db];
        if (it == 0){
            add += (d[v] == 0 && mb[v] == 0);
            add += (d[v] == 0 && mf[v] + val[c] == 0);
        }
    } else if (min(d[v], mb[v]) >= 0)
        cnt[sz[c] + d[v]]++;
    for (int ch : g[v]){
        if (ch == p || vis[ch])
            continue;
        dfs2(ch, v, b);
    }
}

void rek(int v){
    c = -1;
    dfs1(v, 0);
    c = cen(v, 0);
    dfs1(c, 0);
    add = 0;
    for (it = 0; it < 2; it++){
        for (int i = 0; i <= 2 * sz[c]; i++)
            cnt[i] = 0;
        for (int ch : g[c]){
            if (vis[ch])
                continue;
            dfs2(ch, c, 1);
            dfs2(ch, c, 0);
        }
        reverse(all(g[c]));
    }
    ans += add;
    vis[c] = 1;
    for (int ch : g[c]){
        if (vis[ch])
            continue;
        rek(ch);
    }
}

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

    cin >> n >> s;
    s = '.' + s;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    for (int i = 1; i <= n; i++){
        if (s[i] == '(')
            val[i] = 1;
        else
            val[i] = -1;
    }
    rek(1);
    cout << ans << "\n";
    return 0;
}

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