oj.uz

Submission #821375

# Submission time Handle Problem Language Result Execution time Memory
821375 2023-08-11T09:38:56 Z stefanopulos Zagrade (COI17_zagrade) C++17
100 / 100
 734 ms 54060 KB 
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")

#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[u] > vel / 2)return centroid(u, v, vel);
    }
    return v;
}

ll br = 0;

int dlA[mxN];
int sumA[mxN];

int grB[mxN];
int sumB[mxN];

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

    if(!sumB[v]){
        br += (min(0, dlA[v] + X) >= 0) + (grB[v] >= 0);
    }   

    for(auto u : g[v]){
        if(u != p && !bio[u]){
            dfs(u, v);
        }
    }


}

vector<int> cuvaj;
int kol[2 * mxN + 5];

void calc(int v, int p){
    if(dlA[v] >= sumA[v])br += kol[sumA[v] + mxN];

    if(!grB[v])cuvaj.pb(mxN - sumB[v]);

    for(auto u : g[v]){
        if(u != p && !bio[u]){
            calc(u, v);
        }
    }

}

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

    grB[cen] = min(0, X); sumB[cen] = X; 
    sumA[cen] = 0; dlA[cen] = 0;

    for(auto u : g[cen]){
        if(!bio[u]){
            dfs(u, cen);
        }
    }

    vector<int> svi;
    for(auto u : g[cen]){
        if(!bio[u]){
            calc(u, cen);

            for(auto c : cuvaj){
                kol[c] += 1; svi.pb(c);
            }

            cuvaj.clear();

        }
    }


    for(auto c : svi)kol[c] = 0;
    svi.clear();

    reverse(all(g[cen]));

    for(auto u : g[cen]){
        if(!bio[u]){
            calc(u, cen);

            for(auto c : cuvaj){
                kol[c] += 1; svi.pb(c);
            }

            cuvaj.clear();

        }
    }


    for(auto c : svi)kol[c] = 0;
    svi.clear();

    for(auto u : g[cen]){
        if(!bio[u]){
            decompose(u);
        }
    }


}

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);

    cout << br << '\n';

    return 0;
}
/*

4
(())
1 2
2 3
3 4

5
())((
1 2
2 3
2 4
3 5

7
)()()((
1 2
1 3
1 6
2 4
4 5
5 7

// probati bojenje sahovski
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 46728 KB Output is correct
2 Correct 285 ms 46644 KB Output is correct
3 Correct 279 ms 46700 KB Output is correct
4 Correct 275 ms 46628 KB Output is correct
5 Correct 289 ms 46736 KB Output is correct
6 Correct 286 ms 47792 KB Output is correct
7 Correct 283 ms 46656 KB Output is correct
8 Correct 299 ms 47816 KB Output is correct
9 Correct 291 ms 46744 KB Output is correct
10 Correct 268 ms 49800 KB Output is correct
11 Correct 300 ms 48388 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7476 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7480 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7424 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 3 ms 7380 KB Output is correct
11 Correct 272 ms 46728 KB Output is correct
12 Correct 285 ms 46644 KB Output is correct
13 Correct 279 ms 46700 KB Output is correct
14 Correct 275 ms 46628 KB Output is correct
15 Correct 289 ms 46736 KB Output is correct
16 Correct 286 ms 47792 KB Output is correct
17 Correct 283 ms 46656 KB Output is correct
18 Correct 299 ms 47816 KB Output is correct
19 Correct 291 ms 46744 KB Output is correct
20 Correct 268 ms 49800 KB Output is correct
21 Correct 300 ms 48388 KB Output is correct
22 Correct 733 ms 24640 KB Output is correct
23 Correct 734 ms 24508 KB Output is correct
24 Correct 612 ms 24404 KB Output is correct
25 Correct 686 ms 24204 KB Output is correct
26 Correct 343 ms 31196 KB Output is correct
27 Correct 386 ms 32036 KB Output is correct
28 Correct 384 ms 30636 KB Output is correct
29 Correct 272 ms 54060 KB Output is correct
30 Correct 286 ms 54032 KB Output is correct
31 Correct 67 ms 29748 KB Output is correct
32 Correct 262 ms 52588 KB Output is correct