oj.uz

Submission #545277

# Submission time Handle Problem Language Result Execution time Memory
545277 2022-04-04T06:54:13 Z tranxuanbach Zagrade (COI17_zagrade) C++17
100 / 100
 1493 ms 86164 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

template <class T>
using ordered_multiset = tree <T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 5;

int n;
string s; int val[N];
vi adj[N];

int par[N], sz[N];

int ctall;
vi adjct[N];
int parct[N], hct[N];

bool block[N];

void dfs_cpn_ct(int u){
    sz[u] = 1;
    Fora(v, adj[u]){
        if (v == par[u] or block[v]){
            continue;
        }
        par[v] = u;
        dfs_cpn_ct(v);
        sz[u] += sz[v];
    }
}

int dfs_ct(int u){
    par[u] = 0;
    dfs_cpn_ct(u);
    if (sz[u] == 1){
        return u;
    }
    int sz_cpn = sz[u];
    while (1){
        int v = 0;
        Fora(tv, adj[u]){
            if (tv == par[u] or block[tv]){
                continue;
            }
            if (sz[tv] * 2 > sz_cpn){
                v = tv;
                break;
            }
        }
        if (v == 0){
            break;
        }
        u = v;
    }
    block[u] = 1;
    Fora(v, adj[u]){
        if (block[v]){
            continue;
        }
        v = dfs_ct(v);
        adjct[u].emplace_back(v);
        parct[v] = u;
    }
    return u;
}

ll ans;

void dfs_cpn_bracket_count(int u, int sum, int mnprefup, int mnprefdown, ordered_multiset <int> &mtsup, ordered_multiset <int> &mtsdown){
    if (sum >= 0 and mnprefup >= 0){
        ans += mtsdown.order_of_key(sum + 1) - mtsdown.order_of_key(sum);
    }
    if (sum <= 0 and mnprefdown == sum){
        ans += mtsup.order_of_key(-sum + 1) - mtsup.order_of_key(-sum);
    }
    Fora(v, adj[u]){
        if (v == par[u] or block[v]){
            continue;
        }
        par[v] = u;
        dfs_cpn_bracket_count(v, sum + val[v], min(val[v], mnprefup + val[v]), min(mnprefdown, sum + val[v]), mtsup, mtsdown);
    }
}

void dfs_cpn_bracket_insert(int u, int sum, int mnprefup, int mnprefdown, ordered_multiset <int> &mtsup, ordered_multiset <int> &mtsdown){
    if (sum >= 0 and mnprefup >= 0){
        mtsup.insert(sum);
    }
    if (sum <= 0 and mnprefdown == sum){
        mtsdown.insert(-sum);
    }
    Fora(v, adj[u]){
        if (v == par[u] or block[v]){
            continue;
        }
        par[v] = u;
        dfs_cpn_bracket_insert(v, sum + val[v], min(val[v], mnprefup + val[v]), min(mnprefdown, sum + val[v]), mtsup, mtsdown);
    }
}

void dfs_bracket(int u){
    ordered_multiset <int> mtsup, mtsdown;
    if (val[u] == 1){
        mtsup.insert(1);
    }
    else{
        mtsdown.insert(1);
    }
    par[u] = 0;
    Fora(v, adj[u]){
        if (block[v]){
            continue;
        }
        par[v] = u;
        dfs_cpn_bracket_count(v, val[v], min(val[v], 0), min(val[v], 0), mtsup, mtsdown);
        dfs_cpn_bracket_insert(v, val[u] + val[v], min({0, val[v], val[v] + val[u]}), min({0, val[u], val[u] + val[v]}), mtsup, mtsdown);
    }
    block[u] = 1;
    Fora(v, adjct[u]){
        dfs_bracket(v);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n;
    cin >> s; s = ' ' + s;
    For(i, 1, n){
        int u, v; cin >> u >> v;
        adj[u].emplace_back(v); adj[v].emplace_back(u);
    }

    ForE(i, 1, n){
        val[i] = (s[i] == '(' ? 1 : -1);
    }
    ctall = dfs_ct(1);
    memset(block, 0, sizeof(block));
    dfs_bracket(ctall);
    cout << ans << endl;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14736 KB Output is correct
2 Correct 9 ms 14828 KB Output is correct
3 Correct 8 ms 14804 KB Output is correct
4 Correct 8 ms 14804 KB Output is correct
5 Correct 8 ms 14804 KB Output is correct
6 Correct 8 ms 14804 KB Output is correct
7 Correct 9 ms 14856 KB Output is correct
8 Correct 9 ms 14804 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 8 ms 14744 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 58316 KB Output is correct
2 Correct 869 ms 73992 KB Output is correct
3 Correct 488 ms 58376 KB Output is correct
4 Correct 809 ms 70916 KB Output is correct
5 Correct 527 ms 58468 KB Output is correct
6 Correct 646 ms 64812 KB Output is correct
7 Correct 487 ms 58424 KB Output is correct
8 Correct 609 ms 64820 KB Output is correct
9 Correct 513 ms 58404 KB Output is correct
10 Correct 1214 ms 86024 KB Output is correct
11 Correct 1493 ms 86016 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14736 KB Output is correct
2 Correct 9 ms 14828 KB Output is correct
3 Correct 8 ms 14804 KB Output is correct
4 Correct 8 ms 14804 KB Output is correct
5 Correct 8 ms 14804 KB Output is correct
6 Correct 8 ms 14804 KB Output is correct
7 Correct 9 ms 14856 KB Output is correct
8 Correct 9 ms 14804 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 8 ms 14744 KB Output is correct
11 Correct 502 ms 58316 KB Output is correct
12 Correct 869 ms 73992 KB Output is correct
13 Correct 488 ms 58376 KB Output is correct
14 Correct 809 ms 70916 KB Output is correct
15 Correct 527 ms 58468 KB Output is correct
16 Correct 646 ms 64812 KB Output is correct
17 Correct 487 ms 58424 KB Output is correct
18 Correct 609 ms 64820 KB Output is correct
19 Correct 513 ms 58404 KB Output is correct
20 Correct 1214 ms 86024 KB Output is correct
21 Correct 1493 ms 86016 KB Output is correct
22 Correct 1380 ms 45108 KB Output is correct
23 Correct 1372 ms 45508 KB Output is correct
24 Correct 1279 ms 43808 KB Output is correct
25 Correct 1326 ms 44764 KB Output is correct
26 Correct 621 ms 42616 KB Output is correct
27 Correct 664 ms 40168 KB Output is correct
28 Correct 675 ms 38400 KB Output is correct
29 Correct 1236 ms 86012 KB Output is correct
30 Correct 1168 ms 86080 KB Output is correct
31 Correct 356 ms 52576 KB Output is correct
32 Correct 1360 ms 86164 KB Output is correct