oj.uz

Submission #250822

# Submission time Handle Problem Language Result Execution time Memory
250822 2020-07-19T09:06:03 Z ne4eHbKa Zagrade (COI17_zagrade) C++17
100 / 100
 2063 ms 79992 KB 
//{ <defines>
#include <bits/stdc++.h>
using namespace std;

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

int md = 998244353;

inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}

int m_bpow(ll A, ll b) {
    int a = A % md;
    ll ans = 1;
    for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
        (ans *= ans) %= md;
        if(p & b)
            (ans *= a) %= md;
    }
    re ans;
}

//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 3e5 + 5;

int f[N], n, si[N];
list<int> g[N];
ll ans;

void sizes(int v, int pr = -1) {
    si[v] = 1;
    for(int u : g[v]) {
        if(u == pr) continue;
        sizes(u, v);
        si[v] += si[u];
    }
}

int centroid(int n, int v, int pr = -1) {
    for(int u : g[v]) {
        if(u == pr || (si[u] << 1) < n) continue;
        return centroid(n, u, v);
    }
    return v;
}

template<typename t>
void rec(t &cl, t &op, int v, int pr, int b = 0, int mn = 0, int mx = 0) {
    b += f[v];
    umax(mx, b);
    umin(mn, b);
    if(b - mx >= 0) op[b]++;
    if(b - mn <= 0) cl[b]++;
    for(int u : g[v]) if(u != pr)
        rec(cl, op, u, v, b, mn, mx);
}

void make(int v) {
    int m = g[v].size();
    map<int, int> c, cl[m], op[m];
    int i = 0;
    for(int u : g[v]) {
        rec(cl[i], op[i], u, v);
        for(const auto &j : cl[i]) c[j.ft] += j.sd;
        ans += f[v] < 0 ? op[i][1] : cl[i][-1];
        i++;
    }
    fo(m) {
        for(const auto &j : op[i]) {
            int b = -(j.ft + f[v]);
            ans += 1ll * j.sd * (c[b] - cl[i][b]);
        }
    }
}

void centree(int v) {
    for(int u : g[v]) g[u].remove(v);
    sizes(v);
    make(v);
    for(int u : g[v])
        centree(centroid(si[u], u));
}

void solve() {
    cin >> n;
    fo(n) {
        char c; cin >> c;
        f[i] = c == '(' ? +1 : -1;
        g[i].clear();
    }
    fo(n - 1) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].pb(y);
        g[y].pb(x);
    }
    ans = 0;
    sizes(0);
    centree(centroid(n, 0));
    cout << ans << endl;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    for(int test = 1; test <= tests; ++test) {
		cerr << "case #" << test << endl;
        solve();
        cerr << endl;
    }
#else
//    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#endif
    return 0;
}

Compilation message

zagrade.cpp: In function 'int m_bpow(ll, ll)':
zagrade.cpp:50:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 51592 KB Output is correct
2 Correct 783 ms 60024 KB Output is correct
3 Correct 470 ms 51704 KB Output is correct
4 Correct 700 ms 57848 KB Output is correct
5 Correct 476 ms 51832 KB Output is correct
6 Correct 629 ms 56568 KB Output is correct
7 Correct 480 ms 51704 KB Output is correct
8 Correct 632 ms 56696 KB Output is correct
9 Correct 463 ms 51704 KB Output is correct
10 Correct 1963 ms 79744 KB Output is correct
11 Correct 355 ms 51568 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7552 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 6 ms 7528 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 6 ms 7456 KB Output is correct
7 Correct 7 ms 7424 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 9 ms 7424 KB Output is correct
10 Correct 5 ms 7552 KB Output is correct
11 Correct 481 ms 51592 KB Output is correct
12 Correct 783 ms 60024 KB Output is correct
13 Correct 470 ms 51704 KB Output is correct
14 Correct 700 ms 57848 KB Output is correct
15 Correct 476 ms 51832 KB Output is correct
16 Correct 629 ms 56568 KB Output is correct
17 Correct 480 ms 51704 KB Output is correct
18 Correct 632 ms 56696 KB Output is correct
19 Correct 463 ms 51704 KB Output is correct
20 Correct 1963 ms 79744 KB Output is correct
21 Correct 355 ms 51568 KB Output is correct
22 Correct 983 ms 32632 KB Output is correct
23 Correct 829 ms 32632 KB Output is correct
24 Correct 828 ms 32672 KB Output is correct
25 Correct 841 ms 32760 KB Output is correct
26 Correct 494 ms 39292 KB Output is correct
27 Correct 515 ms 36368 KB Output is correct
28 Correct 550 ms 35220 KB Output is correct
29 Correct 2063 ms 79864 KB Output is correct
30 Correct 1929 ms 79992 KB Output is correct
31 Correct 180 ms 66552 KB Output is correct
32 Correct 342 ms 51576 KB Output is correct