oj.uz

Submission #819930

# Submission time Handle Problem Language Result Execution time Memory
819930 2023-08-10T15:55:30 Z stefanopulos Zagrade (COI17_zagrade) C++17
40 / 100
 3000 ms 58928 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ldb;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ldb,ldb> pdd;

#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for(auto& a : x)
 
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 300005; 

int n;
string s;

vector<int> g[mxN];

int cnt[mxN];
bool bio[mxN];
void dfs_cnt(int v, int p){
    cnt[v] = 1;
    for(auto u : g[v]){
        if(u != p && !bio[u]){
            dfs_cnt(u, v);
            cnt[v] += cnt[u];
        }
    }
}

int centroid(int v, int p, int vel){
    for(auto u : g[v]){
        if(u == p || bio[u])continue;
        if(cnt[v] > vel / 2)return centroid(u, v, vel);
    }
    return v;
}

ll br = 0;
vector<int> cuvaj;
map<int,vector<int>> kol;

void dfs(int v, int p, int sumA, int dlA, int sumB, int grB, int X, bool f){
    int Y = (s[v] == '(' ? 1 : -1);
    sumA += Y; dlA = min(dlA, sumA);
    sumB += Y; grB = min(0, grB + Y);

    if(kol.count(sumA) == 1){

        int l = 0, r = sz(kol[sumA]) - 1, ans = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(dlA >= kol[sumA][mid]){
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }

        br += ans + 1;

    }    

    if(f == 1){
        if(sumB == 0 && min(0, dlA + X) >= 0)br += 1;
        if(sumB == 0 && grB >= 0)br += 1;
    }

    if(grB == 0)cuvaj.pb(-sumB);
    for(auto u : g[v]){
        if(u != p && !bio[u]){
            dfs(u, v, sumA, dlA, sumB, grB, X, f);
        }
    }


}


void decompose(int v, int p){
    dfs_cnt(v, -1); int cen = centroid(v, -1, cnt[v]);
    bio[cen] = 1; int X = (s[cen] == '(' ? 1 : -1);

    kol.clear();
    for(auto u : g[cen]){
        if(u != p && !bio[u]){
            dfs(u, cen, 0, 0, X, min(0, X), X, 1);
            
            for(auto c : cuvaj)kol[c].pb(c);
            cuvaj.clear();

        }
    }

    reverse(all(g[cen]));

    kol.clear();
    for(auto u : g[cen]){
        if(u != p && !bio[u]){
            dfs(u, cen, 0, 0, X, min(0, X), X, 0);
            
            for(auto c : cuvaj)kol[c].pb(c);
            cuvaj.clear();

        }
    }

    // reverse(all(g[cen]));
    for(auto u : g[cen]){
        if(u != p && !bio[u]){
            decompose(u, cen);
        }
    }


}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> s;
    s = ' ' + s;
    ff(i,1,n - 1){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    decompose(1, -1);

    cout << br << '\n';

    return 0;
}
/*



// probati bojenje sahovski
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7344 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 6 ms 7376 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 6 ms 7380 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 42052 KB Output is correct
2 Correct 277 ms 41916 KB Output is correct
3 Correct 407 ms 42024 KB Output is correct
4 Correct 294 ms 41920 KB Output is correct
5 Correct 392 ms 42212 KB Output is correct
6 Correct 537 ms 44556 KB Output is correct
7 Correct 387 ms 42072 KB Output is correct
8 Correct 503 ms 44652 KB Output is correct
9 Correct 412 ms 42008 KB Output is correct
10 Correct 740 ms 58928 KB Output is correct
11 Correct 367 ms 43620 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7344 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 6 ms 7376 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 6 ms 7380 KB Output is correct
11 Correct 389 ms 42052 KB Output is correct
12 Correct 277 ms 41916 KB Output is correct
13 Correct 407 ms 42024 KB Output is correct
14 Correct 294 ms 41920 KB Output is correct
15 Correct 392 ms 42212 KB Output is correct
16 Correct 537 ms 44556 KB Output is correct
17 Correct 387 ms 42072 KB Output is correct
18 Correct 503 ms 44652 KB Output is correct
19 Correct 412 ms 42008 KB Output is correct
20 Correct 740 ms 58928 KB Output is correct
21 Correct 367 ms 43620 KB Output is correct
22 Correct 1114 ms 19892 KB Output is correct
23 Correct 906 ms 19524 KB Output is correct
24 Correct 1029 ms 19636 KB Output is correct
25 Correct 981 ms 19380 KB Output is correct
26 Execution timed out 3072 ms 32564 KB Time limit exceeded
27 Halted 0 ms 0 KB -