oj.uz

Submission #370138

# Submission time Handle Problem Language Result Execution time Memory
370138 2021-02-23T11:33:54 Z Nima_Naderi Zagrade (COI17_zagrade) C++14
100 / 100
 1504 ms 49240 KB 
///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

//typedef long long ll;
typedef int ll;
const ll MXN = 3e5 + 10;
ll n, globc;
long long ans;
ll sub[MXN], bal[MXN], minb[MXN], ted[MXN];
vector<ll> adj[MXN];
bool hide[MXN];
string s;
void plant(ll u, ll par){
    sub[u] = 1;
    for(auto v : adj[u]){
        if(v != par && !hide[v]){
            plant(v, u), sub[u] += sub[v];
        }
    }
}
ll CRD(ll u, ll par, ll val){
    for(auto v : adj[u]){
        if(v == par || hide[v]) continue;
        if(sub[v] >= val) return CRD(v, u, val);
    }
    return u;
}
void Upd(ll u, ll par, ll dt){
    if(par == globc) bal[u] = minb[u] = 0;
    else             bal[u] = bal[par], minb[u] = minb[par];
    bal[u] += (s[u] == '(' ? +1 : -1);
    minb[u] = min(minb[u], bal[u]);
    if(bal[u] <= 0 && minb[u] - bal[u] >= 0){
        ted[-bal[u]] += dt;
    }
    for(auto v : adj[u]){
        if(v == par || hide[v]) continue;
        Upd(v, u, dt);
    }
}
void Calc(ll u, ll par, ll b, ll mb){
    b = (s[u] == '(' ? +1 : -1) + b;
    mb = min(0, (s[u] == '(' ? +1 : -1) + mb);
    if(mb >= 0){
        ans += ted[b];
        if(b == 0) ans ++;
    }
    for(auto v : adj[u]){
        if(v == par || hide[v]) continue;
        Calc(v, u, b, mb);
    }
}
void DMS(ll u, ll h){
    plant(u, -1);
    ll cent = CRD(u, -1, (sub[u] + 1) / 2);
    globc = cent;
    for(auto v : adj[cent]){
        if(!hide[v]) Upd(v, cent, +1);
    }
    for(auto v : adj[cent]){
        if(hide[v]) continue;
        ll x = (s[cent] == '(' ? +1 : -1);
        Upd(v, cent, -1);
        Calc(v, cent, x, min(0, x));
        Upd(v, cent, +1);
    }
    if(s[cent] == '(') ans += ted[1];
    for(auto v : adj[cent]){
        if(!hide[v]) Upd(v, cent, -1);
    }
    hide[cent] = 1;
    for(auto v : adj[cent]){
        if(!hide[v]) DMS(v, h + 1);
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> s;
    s = "$" + s;
    for(int i = 1; i < n; i ++){
        ll u, v; cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    DMS(1, 0);
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 6 ms 7404 KB Output is correct
4 Correct 6 ms 7404 KB Output is correct
5 Correct 6 ms 7404 KB Output is correct
6 Correct 6 ms 7404 KB Output is correct
7 Correct 7 ms 7532 KB Output is correct
8 Correct 6 ms 7404 KB Output is correct
9 Correct 6 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 493 ms 48600 KB Output is correct
2 Correct 550 ms 49004 KB Output is correct
3 Correct 502 ms 48600 KB Output is correct
4 Correct 556 ms 48728 KB Output is correct
5 Correct 496 ms 48600 KB Output is correct
6 Correct 497 ms 48600 KB Output is correct
7 Correct 514 ms 48728 KB Output is correct
8 Correct 510 ms 48600 KB Output is correct
9 Correct 496 ms 48600 KB Output is correct
10 Correct 490 ms 49240 KB Output is correct
11 Correct 488 ms 48600 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 6 ms 7404 KB Output is correct
3 Correct 6 ms 7404 KB Output is correct
4 Correct 6 ms 7404 KB Output is correct
5 Correct 6 ms 7404 KB Output is correct
6 Correct 6 ms 7404 KB Output is correct
7 Correct 7 ms 7532 KB Output is correct
8 Correct 6 ms 7404 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 6 ms 7404 KB Output is correct
11 Correct 493 ms 48600 KB Output is correct
12 Correct 550 ms 49004 KB Output is correct
13 Correct 502 ms 48600 KB Output is correct
14 Correct 556 ms 48728 KB Output is correct
15 Correct 496 ms 48600 KB Output is correct
16 Correct 497 ms 48600 KB Output is correct
17 Correct 514 ms 48728 KB Output is correct
18 Correct 510 ms 48600 KB Output is correct
19 Correct 496 ms 48600 KB Output is correct
20 Correct 490 ms 49240 KB Output is correct
21 Correct 488 ms 48600 KB Output is correct
22 Correct 1476 ms 25304 KB Output is correct
23 Correct 1427 ms 25304 KB Output is correct
24 Correct 1444 ms 25432 KB Output is correct
25 Correct 1504 ms 25364 KB Output is correct
26 Correct 630 ms 32856 KB Output is correct
27 Correct 635 ms 29400 KB Output is correct
28 Correct 667 ms 28224 KB Output is correct
29 Correct 485 ms 49112 KB Output is correct
30 Correct 493 ms 49176 KB Output is correct
31 Correct 102 ms 25044 KB Output is correct
32 Correct 486 ms 48600 KB Output is correct