oj.uz

Submission #969189

# Submission time Handle Problem Language Result Execution time Memory
969189 2024-04-24T16:14:49 Z Beerus13 Zagrade (COI17_zagrade) C++14
100 / 100
 786 ms 39944 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 5;

int n, a[N], sz[N], cnt[N];
bool del[N];
vector<int> g[N];
ll ans;

int dfs_size(int u, int p = 0) {
    sz[u] = 1;
    for(int v : g[u]) if(v != p && !del[v]) sz[u] += dfs_size(v, u);
    return sz[u];
}

int find_centroid(int u, int p, int num) {
    for(int v : g[u]) if(v != p && !del[v] && sz[v] > num / 2) return find_centroid(v, u, num);
    return u;
}

void dfs_open(int u, int p = 0, int val = 0, int num_close = 0) {
    num_close = max(num_close, 0);
    if(a[u] == -1) ++num_close;
    else --num_close;
    val += a[u];
    if(num_close <= 0) {
        ans += cnt[val];
    }
    for(int v : g[u]) if(v != p && !del[v]) {
        dfs_open(v, u, val, num_close);
    }
}

void dfs_close(int add, int u, int p = 0, int val = 0, int num_open = 0) {
    num_open = max(num_open, 0);
    if(a[u] == 1) {
        ++num_open;
        --val;
    }
    else {
        --num_open;
        ++val;
    }
    if(num_open <= 0) {
        cnt[val] += add;
    }
    for(int v : g[u]) if(v != p && !del[v]) {
        dfs_close(add, v, u, val, num_open);
    }
}

void decomposition(int u) {
    u = find_centroid(u, 0, dfs_size(u));
    del[u] = 1;
    dfs_close(1, u);
    ans += cnt[0];
    for(int v : g[u]) if(!del[v]) {
        dfs_close(-1, v, u, -a[u], a[u]);
        dfs_open(v, u);
        dfs_close(1, v, u, -a[u], a[u]);
    }
    dfs_close(-1, u);
    for(int v : g[u]) if(!del[v]) {
        decomposition(v);
    }
}

void solve() {
    cin >> n;
    string s; cin >> s;
    for(int i = 0; i < s.size(); ++i) {
        a[i + 1] = s[i] == '(' ? 1 : -1;
    }
    for(int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    decomposition(1);
    cout << ans << '\n';
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

// https://oj.uz/problem/view/COI17_zagrade

Compilation message

zagrade.cpp: In function 'void solve()':
zagrade.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 0; i < s.size(); ++i) {
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 11096 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 39652 KB Output is correct
2 Correct 360 ms 39652 KB Output is correct
3 Correct 395 ms 39580 KB Output is correct
4 Correct 412 ms 39672 KB Output is correct
5 Correct 390 ms 39728 KB Output is correct
6 Correct 421 ms 39652 KB Output is correct
7 Correct 387 ms 39944 KB Output is correct
8 Correct 403 ms 39728 KB Output is correct
9 Correct 387 ms 39652 KB Output is correct
10 Correct 341 ms 39656 KB Output is correct
11 Correct 315 ms 39652 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 11096 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 392 ms 39652 KB Output is correct
12 Correct 360 ms 39652 KB Output is correct
13 Correct 395 ms 39580 KB Output is correct
14 Correct 412 ms 39672 KB Output is correct
15 Correct 390 ms 39728 KB Output is correct
16 Correct 421 ms 39652 KB Output is correct
17 Correct 387 ms 39944 KB Output is correct
18 Correct 403 ms 39728 KB Output is correct
19 Correct 387 ms 39652 KB Output is correct
20 Correct 341 ms 39656 KB Output is correct
21 Correct 315 ms 39652 KB Output is correct
22 Correct 656 ms 21096 KB Output is correct
23 Correct 613 ms 21228 KB Output is correct
24 Correct 620 ms 21224 KB Output is correct
25 Correct 786 ms 21220 KB Output is correct
26 Correct 468 ms 27108 KB Output is correct
27 Correct 452 ms 24368 KB Output is correct
28 Correct 469 ms 23268 KB Output is correct
29 Correct 304 ms 39716 KB Output is correct
30 Correct 305 ms 39656 KB Output is correct
31 Correct 65 ms 22076 KB Output is correct
32 Correct 332 ms 39528 KB Output is correct