oj.uz

Submission #960436

# Submission time Handle Problem Language Result Execution time Memory
960436 2024-04-10T13:07:30 Z Blagoj Zagrade (COI17_zagrade) C++17
100 / 100
 650 ms 46272 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 10744 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 3 ms 10584 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 43876 KB Output is correct
2 Correct 421 ms 46264 KB Output is correct
3 Correct 431 ms 44100 KB Output is correct
4 Correct 446 ms 46272 KB Output is correct
5 Correct 445 ms 44048 KB Output is correct
6 Correct 431 ms 44168 KB Output is correct
7 Correct 441 ms 43960 KB Output is correct
8 Correct 444 ms 44132 KB Output is correct
9 Correct 446 ms 43960 KB Output is correct
10 Correct 321 ms 45248 KB Output is correct
11 Correct 375 ms 43964 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 3 ms 10744 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 3 ms 10584 KB Output is correct
11 Correct 432 ms 43876 KB Output is correct
12 Correct 421 ms 46264 KB Output is correct
13 Correct 431 ms 44100 KB Output is correct
14 Correct 446 ms 46272 KB Output is correct
15 Correct 445 ms 44048 KB Output is correct
16 Correct 431 ms 44168 KB Output is correct
17 Correct 441 ms 43960 KB Output is correct
18 Correct 444 ms 44132 KB Output is correct
19 Correct 446 ms 43960 KB Output is correct
20 Correct 321 ms 45248 KB Output is correct
21 Correct 375 ms 43964 KB Output is correct
22 Correct 610 ms 25292 KB Output is correct
23 Correct 578 ms 25536 KB Output is correct
24 Correct 623 ms 25280 KB Output is correct
25 Correct 650 ms 25300 KB Output is correct
26 Correct 491 ms 31416 KB Output is correct
27 Correct 482 ms 28608 KB Output is correct
28 Correct 490 ms 27712 KB Output is correct
29 Correct 285 ms 45244 KB Output is correct
30 Correct 319 ms 45272 KB Output is correct
31 Correct 58 ms 25028 KB Output is correct
32 Correct 349 ms 43972 KB Output is correct