oj.uz

Submission #553083

# Submission time Handle Problem Language Result Execution time Memory
553083 2022-04-24T15:35:08 Z hoanghq2004 Zagrade (COI17_zagrade) C++14
100 / 100
 1086 ms 54492 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

int n, sz[N], big[N], c[N], del[N];
vector <int> g[N];

void dfs(int u, int p) {
    sz[u] = 1, big[u] = 0;
    for (auto v: g[u]) {
        if (v == p || del[v]) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] >= sz[big[u]]) big[u] = v;
    }
}

int cnt[N * 2];

int centroid(int u) {
    dfs(u, 0);
    int num = sz[u] / 2;
    while (sz[big[u]] > num) u = big[u];
    return u;
}

void add(int u, int p, int s, int d) {
    if (d >= 0) ++cnt[s + N];
    for (auto v: g[u]) {
        if (v == p || del[v]) continue;
        add(v, u, s + c[v], min(d + c[v], c[v]));
    }
}

long long ans;

void calc(int u, int p, int s, int d) {
    if (d >= s) ans += cnt[N - s];
    for (auto v: g[u]) {
        if (v == p || del[v]) continue;
        calc(v, u, s + c[v], min(d, s + c[v]));
    }
}


void rev(int u, int p, int s, int d) {
    if (d >= 0) --cnt[s + N];
    for (auto v: g[u]) {
        if (v == p || del[v]) continue;
        rev(v, u, s + c[v], min(d + c[v], c[v]));
    }
}

void build(int u) {
    u = centroid(u);
    if (c[u] >= 0) ++cnt[c[u] + N];
    for (auto v: g[u]) {
        if (del[v]) continue;
        calc(v, u, c[v], min(0, c[v]));
        add(v, u, c[u] + c[v], min({0, c[u] + c[v], c[v]}));
    }
    for (auto v: g[u]) {
        if (del[v]) continue;
        rev(v, u, c[u] + c[v], min({0, c[u] + c[v], c[v]}));
    }
    if (c[u] >= 0) --cnt[c[u] + N];
    reverse(g[u].begin(), g[u].end());
    for (auto v: g[u]) {
        if (del[v]) continue;
        calc(v, u, c[v], min(0, c[v]));
        add(v, u, c[u] + c[v], min({0, c[u] + c[v], c[v]}));
    }
    ans += cnt[N];
    for (auto v: g[u]) {
        if (del[v]) continue;
        rev(v, u, c[u] + c[v], min({0, c[u] + c[v], c[v]}));
    }
    del[u] = 1;
    for (auto v: g[u])
        if (!del[v]) build(v);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int u = 1; u <= n; ++u) {
        char ch;
        cin >> ch;
        c[u] = (ch == '(' ? 1 : -1);
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build(1);
    cout << ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 49620 KB Output is correct
2 Correct 522 ms 49764 KB Output is correct
3 Correct 528 ms 53792 KB Output is correct
4 Correct 523 ms 53776 KB Output is correct
5 Correct 530 ms 53856 KB Output is correct
6 Correct 551 ms 53964 KB Output is correct
7 Correct 519 ms 53824 KB Output is correct
8 Correct 560 ms 53784 KB Output is correct
9 Correct 522 ms 53784 KB Output is correct
10 Correct 473 ms 54392 KB Output is correct
11 Correct 490 ms 53816 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 517 ms 49620 KB Output is correct
12 Correct 522 ms 49764 KB Output is correct
13 Correct 528 ms 53792 KB Output is correct
14 Correct 523 ms 53776 KB Output is correct
15 Correct 530 ms 53856 KB Output is correct
16 Correct 551 ms 53964 KB Output is correct
17 Correct 519 ms 53824 KB Output is correct
18 Correct 560 ms 53784 KB Output is correct
19 Correct 522 ms 53784 KB Output is correct
20 Correct 473 ms 54392 KB Output is correct
21 Correct 490 ms 53816 KB Output is correct
22 Correct 1071 ms 25820 KB Output is correct
23 Correct 1035 ms 25904 KB Output is correct
24 Correct 1041 ms 25808 KB Output is correct
25 Correct 1086 ms 25820 KB Output is correct
26 Correct 773 ms 35004 KB Output is correct
27 Correct 774 ms 30808 KB Output is correct
28 Correct 780 ms 29276 KB Output is correct
29 Correct 485 ms 54476 KB Output is correct
30 Correct 483 ms 54492 KB Output is correct
31 Correct 90 ms 25364 KB Output is correct
32 Correct 478 ms 53828 KB Output is correct