oj.uz

Submission #390761

# Submission time Handle Problem Language Result Execution time Memory
390761 2021-04-16T21:17:32 Z dolphingarlic Zagrade (COI17_zagrade) C++14
100 / 100
 1154 ms 48476 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int fwd[300001], rev[300001], subtree[300001];
vector<int> graph[300001];
ll ans = 0;
bool processed[300001];

int get_subtree_sizes(int node, int parent = 0) {
    subtree[node] = 1;
    for (int i : graph[node])
        if (i != parent && !processed[i])
            subtree[node] += get_subtree_sizes(i, node);
    return subtree[node];
}

int get_centroid(int node, int target, int parent = 0) {
    for (int i : graph[node])
        if (i != parent && !processed[i] && subtree[i] > target)
            return get_centroid(i, target, node);
    return node;
}

void calc(int node, int parent, int *v, vector<int> &cnt, int curr, int mn) {
    curr += v[node];
    mn = min(0, mn + v[node]);

    if (mn == 0) ans += cnt[curr];
    for (int i : graph[node])
        if (i != parent && !processed[i]) calc(i, node, v, cnt, curr, mn);
}

void upd(int node, int parent, int *v, vector<int> &cnt, int curr, int mn) {
    curr += v[node];
    mn = min(0, mn + v[node]);

    if (mn == 0) cnt[curr]++;
    for (int i : graph[node])
        if (i != parent && !processed[i]) upd(i, node, v, cnt, curr, mn);
}

void decompose(int node = 1) {
    int sz = get_subtree_sizes(node);
    int centroid = get_centroid(node, sz / 2);

    vector<int> cnt_fwd(sz + 2), cnt_rev(sz + 2);
    if (fwd[centroid] == 1)
        cnt_fwd[1]++;
    else
        cnt_rev[1]++;
    for (int i : graph[centroid])
        if (!processed[i]) {
            calc(i, centroid, fwd, cnt_rev, 0, 0);
            calc(i, centroid, rev, cnt_fwd, 0, 0);
            upd(i, centroid, fwd, cnt_fwd, fwd[centroid],
                min(0, fwd[centroid]));
            upd(i, centroid, rev, cnt_rev, rev[centroid],
                min(0, rev[centroid]));
        }

    processed[centroid] = true;
    for (int i : graph[centroid])
        if (!processed[i]) decompose(i);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        if (c == '(')
            fwd[i] = 1, rev[i] = -1;
        else
            fwd[i] = -1, rev[i] = 1;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    decompose();
    cout << ans;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 43992 KB Output is correct
2 Correct 460 ms 48156 KB Output is correct
3 Correct 460 ms 48236 KB Output is correct
4 Correct 488 ms 48216 KB Output is correct
5 Correct 460 ms 48196 KB Output is correct
6 Correct 452 ms 48196 KB Output is correct
7 Correct 458 ms 48228 KB Output is correct
8 Correct 476 ms 48328 KB Output is correct
9 Correct 444 ms 48160 KB Output is correct
10 Correct 448 ms 48156 KB Output is correct
11 Correct 442 ms 48184 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 6 ms 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 6 ms 7420 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 6 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 453 ms 43992 KB Output is correct
12 Correct 460 ms 48156 KB Output is correct
13 Correct 460 ms 48236 KB Output is correct
14 Correct 488 ms 48216 KB Output is correct
15 Correct 460 ms 48196 KB Output is correct
16 Correct 452 ms 48196 KB Output is correct
17 Correct 458 ms 48228 KB Output is correct
18 Correct 476 ms 48328 KB Output is correct
19 Correct 444 ms 48160 KB Output is correct
20 Correct 448 ms 48156 KB Output is correct
21 Correct 442 ms 48184 KB Output is correct
22 Correct 1099 ms 29084 KB Output is correct
23 Correct 1091 ms 29192 KB Output is correct
24 Correct 1098 ms 28880 KB Output is correct
25 Correct 1154 ms 29068 KB Output is correct
26 Correct 531 ms 35796 KB Output is correct
27 Correct 543 ms 33152 KB Output is correct
28 Correct 561 ms 31884 KB Output is correct
29 Correct 457 ms 48132 KB Output is correct
30 Correct 454 ms 48416 KB Output is correct
31 Correct 111 ms 27960 KB Output is correct
32 Correct 444 ms 48476 KB Output is correct