oj.uz

Submission #894963

# Submission time Handle Problem Language Result Execution time Memory
894963 2023-12-29T09:53:01 Z vjudge1 Zagrade (COI17_zagrade) C++17
10 / 100
 39 ms 21516 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 1e5 + 2;
const int M = 7e6 + 1;
int mod0 = 1e9+7, mod1 = 1e9+9;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 31;

int mult(int a, int b, int mod) {
    return a * 1LL * b % mod;
}

int sum(int a, int b, int mod) {
    a %= mod; 
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}

ll binpow(ll a, ll n, int mod) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1, mod) * a % mod;
    } else {
        ll b = binpow(a, n / 2, mod);
        return b * b % mod;
    }
}

vector<int> g[N], ng[N];
int pc[N], used[N], sz[N], par[N], d[N];

void recalcsz(int v, int p){
    sz[v] = 1;
    for(auto u : g[v]){
        if(u != p && !used[u]){
            recalcsz(u, v);
            sz[v] += sz[u];
        }
    }
}

int getcentroid(int v, int p, int wh){
    for(auto u : g[v]){
        if(u != p && !used[u] && sz[u] > (wh / 2))
            return getcentroid(u, v, wh);
    }
    return v;
}

void decompose(int v, int p, int dp = 1){
    pc[v] = p;
    used[v] = 1;
    d[v] = dp;
    for(auto u : g[v]){
        if(!used[u]){
            recalcsz(u, -1);
            int c = getcentroid(u, -1, sz[u]);
            decompose(c, v, dp + 1);
        }
    }
}

map<pii, pii> mp, mp1;
string s;

int ans;
vector<int> dfs1(int v){
    vector<int> vs[sz(ng[v])];
    map<int, int> mpp;
    vector<int> ret = {v};
    for(int i = 0; i < sz(ng[v]); i++){
        vs[i] = dfs1(ng[v][i]);
        for(auto u : vs[i]){
            ret.pb(u);
            if(mp[{u, v}].S >= 0){
                if(s[v] == ')' && mp[{u, v}].F == 1)
                    ans++;
                ans += mpp[-mp[{u, v}].F];
            }
        }
        for(auto u : vs[i]){
            if(mp1[{v, u}].S >= mp1[{v, u}].F){
                mpp[mp1[{v, u}].F]++;
                if(mp1[{v, u}].F == 0)
                    ans++;
            }
        }
    }

    mpp.clear();
    for(int i = sz(ng[v]) - 1; i >= 0; i--){
        for(auto u : vs[i]){
            if(mp[{u, v}].S >= 0){
                ans += mpp[-mp[{u, v}].F];
            }
        }
        for(auto u : vs[i]){
            if(mp1[{v, u}].S >= mp1[{v, u}].F)
                mpp[mp1[{v, u}].F]++;
        }
    }
    return ret;
}

void nudela(int v, int p, int r, int c, int mn){
    if(s[v] == '(')
        c++;
    else
        c--;
    mn = min(mn, c);
    mp1[{r, v}] = {c, mn};
    for(auto u : g[v]){
        if(u != p && d[u] > d[r])
            nudela(u, v, r, c, mn);
    }
}

void neveroyatno(int v, int p, int r, int ver, int mn){
    if(v != r){
        if(s[v] == '(')
            mn = min(mn + 1, 0LL), ver++;
        else
            mn = min(mn - 1, -1LL), ver--;
        mp[{v, r}] = {ver, mn};
    }
    for(auto u : g[v]){
        if(d[u] > d[r] && u != p)
            neveroyatno(u, v, r, ver, mn);
    }
}

void solve(){
    int n;
    cin >> n;
    cin >> s;
    s = "#" + s;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    recalcsz(1, -1);
    int c = getcentroid(1, -1, sz[1]);
    decompose(c, -1);
    for(int i = 1; i <= n; i++)
        ng[pc[i]].pb(i);
    for(int i = 1; i <= n; i++)
        nudela(i, -1, i, 0, 0);
    for(int i = 1; i <= n; i++)
        neveroyatno(i, -1, i, 0, 0);
    /*for(int i = 1; i <= n; i++)
        cout << d[i] << ' ';
    //cout << '\n';
    for(auto e : mp){
        //cout << e.F.F << ' ' << e.F.S << ' ' << e.S.F << ' ' << e.S.S << '\n';
    }
    //cout << '\n';
    for(auto e : mp1){
        //cout << e.F.F << ' ' << e.F.S << ' ' << e.S.F << ' ' << e.S.S << '\n';
    }*/
    dfs1(c);
    cout << ans << '\n';
}   

signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9820 KB Output is correct
2 Correct 8 ms 9820 KB Output is correct
3 Correct 7 ms 9820 KB Output is correct
4 Correct 7 ms 9680 KB Output is correct
5 Correct 7 ms 9564 KB Output is correct
6 Correct 7 ms 9700 KB Output is correct
7 Correct 8 ms 9820 KB Output is correct
8 Correct 7 ms 9840 KB Output is correct
9 Correct 7 ms 10072 KB Output is correct
10 Correct 3 ms 9308 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 21516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9820 KB Output is correct
2 Correct 8 ms 9820 KB Output is correct
3 Correct 7 ms 9820 KB Output is correct
4 Correct 7 ms 9680 KB Output is correct
5 Correct 7 ms 9564 KB Output is correct
6 Correct 7 ms 9700 KB Output is correct
7 Correct 8 ms 9820 KB Output is correct
8 Correct 7 ms 9840 KB Output is correct
9 Correct 7 ms 10072 KB Output is correct
10 Correct 3 ms 9308 KB Output is correct
11 Runtime error 39 ms 21516 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -