Submission #894977

#	Time	Username	Problem	Language	Result	Execution time	Memory
894977		vjudge1	Zagrade (COI17_zagrade)	C++17	40 / 100	3099 ms	736040 KiB

zagrade

#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 = 3e5 + 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], 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);
        }
    }
}

unordered_map<int, pii> mp[N], mp1[N];
string s = "";

int ans;
vector<int> dfs1(int v){
    vector<int> vs[sz(ng[v])];
    unordered_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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60