oj.uz

Submission #377610

# Submission time Handle Problem Language Result Execution time Memory
377610 2021-03-14T11:35:46 Z Sara Zagrade (COI17_zagrade) C++14
100 / 100
 1570 ms 48600 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define F first
#define S second
#define pb push_back

const int N = 3e5 + 10;
const int LOG = 25;
const int MOD = 1e9 + 7;
const ll  inf = 1e9 + 5;

int n, m;
vector <int> g[N];
int a[N];
string s;

int sz[N];
bool dead[N];
ll cnt[N];

void dfs(int v, int p){
    sz[v] = 1;
    for (int u : g[v]){
        if (u == p || dead[u]) continue;
        dfs(u, v); 
        sz[v] += sz[u];
    }
    return;
}

int find_centr(int v, int p, int root){
    for (int u : g[v]){
        if (u == p || dead[u]) continue;
        if (sz[root] < 2 * sz[u]){
            return find_centr(u, v, root);
        }
    }
    return v;
}

void add(int v, int p, int op, int cl){
    if (a[v] == 1){
        if (cl) cl --;
        else op ++;
    }
    if (a[v] == -1) cl ++;
    if (cl == 0) cnt[op] ++;
    for (int u : g[v]){
        if (u == p || dead[u]) continue;
        add(u, v, op, cl);
    }
    return;
}

ll find_ans(int v, int p, int op, int cl){
    ll ret = 0;
    if (a[v] == 1) op ++;
    if (a[v] == -1){
        if (op) op --;
        else cl ++;
    }
    if (op == 0){
        ret += cnt[cl] + (cl == 0);
    }
    for (int u : g[v]){
        if (u == p || dead[u]) continue;
        ret += find_ans(u, v, op, cl);
    }
    return ret;
}

void del(int v, int p, int op, int cl){
    if (a[v] == 1){
        if (cl) cl --;
        else op ++;
    }
    if (a[v] == -1) cl ++;
    if (cl == 0) cnt[op] --;
    for (int u : g[v]){
        if (u == p || dead[u]) continue;
        del(u, v, op, cl);
    }
    return;
}

ll oth(int v, int p, int op, int cl){
    ll ret = 0;
    if (a[v] == 1){
        if (cl) cl --;
        else op ++;
    }
    if (a[v] == -1) cl ++;
    if (op == 0 && cl == 0) ret ++;
    for (int u : g[v]){
        if (u == p || dead[u]) continue;
        ret += oth(u, v, op, cl);
    }
    return ret;
}

ll solve(int v){
    dfs(v, 0);
    v = find_centr(v, 0, v);
    dead[v] = 1;
    ll ret = 0;
    for (int u : g[v]){
        if (dead[u]) continue;
        add(u, v, 0, 0);
    }
    for (int u : g[v]){
        if (dead[u]) continue;
        del(u, v, 0, 0);
        ll res = find_ans(u, v, (a[v] == 1), (a[v] == -1));
        ret += res + oth(u, v, (a[v] == 1), (a[v] == -1));
        add(u, v, 0, 0);
    }
    for (int u : g[v]){
        if (dead[u]) continue;
        del(u, v, 0, 0);
    }
    for (int u : g[v]){
        if (!dead[u]){
            ret += solve(u);
        }
    }
    return ret;
}

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 ++){
        a[i] = ((s[i] == '(') ? 1 : -1);
    }
    for (int i = 0; i < n - 1; i ++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }
    cout << solve(1) << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 43324 KB Output is correct
2 Correct 587 ms 47448 KB Output is correct
3 Correct 636 ms 47576 KB Output is correct
4 Correct 599 ms 47448 KB Output is correct
5 Correct 639 ms 47536 KB Output is correct
6 Correct 643 ms 47704 KB Output is correct
7 Correct 622 ms 47624 KB Output is correct
8 Correct 630 ms 47576 KB Output is correct
9 Correct 624 ms 47336 KB Output is correct
10 Correct 494 ms 48600 KB Output is correct
11 Correct 501 ms 47576 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 6 ms 7532 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 7 ms 7404 KB Output is correct
7 Correct 6 ms 7404 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 7 ms 7404 KB Output is correct
10 Correct 6 ms 7404 KB Output is correct
11 Correct 629 ms 43324 KB Output is correct
12 Correct 587 ms 47448 KB Output is correct
13 Correct 636 ms 47576 KB Output is correct
14 Correct 599 ms 47448 KB Output is correct
15 Correct 639 ms 47536 KB Output is correct
16 Correct 643 ms 47704 KB Output is correct
17 Correct 622 ms 47624 KB Output is correct
18 Correct 630 ms 47576 KB Output is correct
19 Correct 624 ms 47336 KB Output is correct
20 Correct 494 ms 48600 KB Output is correct
21 Correct 501 ms 47576 KB Output is correct
22 Correct 1570 ms 24064 KB Output is correct
23 Correct 1522 ms 24120 KB Output is correct
24 Correct 1456 ms 24152 KB Output is correct
25 Correct 1539 ms 24408 KB Output is correct
26 Correct 773 ms 31704 KB Output is correct
27 Correct 783 ms 28452 KB Output is correct
28 Correct 806 ms 27152 KB Output is correct
29 Correct 494 ms 48600 KB Output is correct
30 Correct 503 ms 48600 KB Output is correct
31 Correct 103 ms 23764 KB Output is correct
32 Correct 505 ms 47420 KB Output is correct