Submission #960436

#	Time	Username	Problem	Language	Result	Execution time	Memory
960436		Blagoj	Zagrade (COI17_zagrade)	C++17	100 / 100	650 ms	46272 KiB

zagrade

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 3e5 + 10;

int n;
string s;
int sz[mxn];
vector<int> g[mxn];
bool processed[mxn];

int getSize(int cur = 1, int par = -1) {
    sz[cur] = 1;
    for (auto x : g[cur]) {
        if (x != par && !processed[x]) sz[cur] += getSize(x, cur);
    }
    return sz[cur];
}

int getCentroid(int cur, int des, int par = -1) {
    for (auto x : g[cur]) {
        if (x != par && !processed[x] && sz[x] >= des) return getCentroid(x, des, cur);
    }
    return cur;
}

ll ans = 0, cntL[mxn], cntR[mxn];
int mx = 0;

// L - side

void get1(int cur, int open, int close, int par = -1) {
    // cout << "?1 " << cur << " " << open << " " << close << " " << par << endl;
    if (close == 0) ans += cntR[open];
    for (auto x : g[cur]) {
        if (x != par && !processed[x]) {
            if (s[x] == '(') {
                if (close) get1(x, open, close - 1, cur);
                else get1(x, open + 1, close, cur);
            }
            if (s[x] == ')') get1(x, open, close + 1, cur);
        }
    }
}

// R - side

void get2(int cur, int open, int close, int par = -1) {
    // cout << "?2 " << cur << " " << open << " " << close << " " << par << endl;
    if (open == 0) ans += cntL[close];
    for (auto x : g[cur]) {
        if (x != par && !processed[x]) {
            if (s[x] == ')') {
                if (open) get2(x, open - 1, close, cur);
                else get2(x, open, close + 1, cur);
            }
            if (s[x] == '(') get2(x, open + 1, close, cur);
        }
    }
}

// L - side

void update1(int cur, int open, int close, int par = -1) {
    // cout << "!1 " << cur << " " << open << " " << close << " " << par << endl;
    if (close == 0) {
        cntL[open]++;
        mx = max(mx, open);
    }
    for (auto x : g[cur]) {
        if (x != par && !processed[x]) {
            if (s[x] == '(') {
                if (close) update1(x, open, close - 1, cur);
                else update1(x, open + 1, close, cur);
            }
            if (s[x] == ')') update1(x, open, close + 1, cur);
        }
    }
}

// R - side

void update2(int cur, int open, int close, int par = -1) {
    // cout << "!2 " << cur << " " << open << " " << close << " " << par << endl;
    if (open == 0) {
        cntR[close]++;
        mx = max(mx, close);
    }
    for (auto x : g[cur]) {
        if (x != par && !processed[x]) {
            if (s[x] == '(') update2(x, open + 1, close, cur);
            if (s[x] == ')') {
                if (open) update2(x, open - 1, close, cur);
                else update2(x, open, close + 1, cur);
            }
        }
    }
}

void decompose(int cur = 1, int par = -1) {
    int centroid = getCentroid(cur, getSize(cur) / 2);
    processed[centroid] = 1;
    cntL[0] = cntR[0] = 1;
    int open = s[centroid] == '(', close = s[centroid] == ')';
    for (auto x : g[centroid]) {
        if (x != par && !processed[x]) {
            if (s[x] == '(') {
                if (close) get1(x, open, close - 1, centroid);
                else get1(x, open + 1, close, centroid);
                get2(x, open + 1, close, centroid);
            }
            if (s[x] == ')') {
                get1(x, open, close + 1, centroid);
                if (open) get2(x, open - 1, close, centroid);
                else get2(x, open, close + 1, centroid);
            }
            if (s[x] == '(') {
                update1(x, 1, 0, centroid);
                update2(x, 1, 0, centroid);
            }
            if (s[x] == ')') {
                update1(x, 0, 1, centroid);
                update2(x, 0, 1, centroid);
            }
        }
    }
    // cout << centroid << " " << ans << endl;
    for (auto x : g[centroid]) {
        if (x != par && !processed[x]) {
            for (int i = 0; i <= mx; i++) cntL[i] = cntR[i] = 0;
            mx = 0;
            decompose(x, centroid);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    cin >> s;
    s = "." + s;
    for (int i = 0; i < n - 1; i++) {
        int f, t;
        cin >> f >> t;
        g[f].push_back(t);
        g[t].push_back(f);
    }
    decompose();
    cout << ans;
}

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