Submission #377610

#	Time	Username	Problem	Language	Result	Execution time	Memory
377610		Sara	Zagrade (COI17_zagrade)	C++14	100 / 100	1570 ms	48600 KiB

zagrade

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60