oj.uz

Submission #969186

# Submission time Handle Problem Language Result Execution time Memory
969186 2024-04-24T16:13:42 Z Beerus13 Zagrade (COI17_zagrade) C++14
100 / 100
 713 ms 111356 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], tmp;
ll ans, cen;

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;
        tmp.push_back(val);
    }
    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));
    cen = 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:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < s.size(); ++i) {
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 3 ms 10952 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10840 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 10892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 61388 KB Output is correct
2 Correct 381 ms 110332 KB Output is correct
3 Correct 387 ms 61756 KB Output is correct
4 Correct 385 ms 111036 KB Output is correct
5 Correct 383 ms 62512 KB Output is correct
6 Correct 425 ms 53304 KB Output is correct
7 Correct 391 ms 61632 KB Output is correct
8 Correct 380 ms 54232 KB Output is correct
9 Correct 387 ms 61336 KB Output is correct
10 Correct 329 ms 111288 KB Output is correct
11 Correct 351 ms 110436 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 3 ms 10952 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10840 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 10892 KB Output is correct
11 Correct 396 ms 61388 KB Output is correct
12 Correct 381 ms 110332 KB Output is correct
13 Correct 387 ms 61756 KB Output is correct
14 Correct 385 ms 111036 KB Output is correct
15 Correct 383 ms 62512 KB Output is correct
16 Correct 425 ms 53304 KB Output is correct
17 Correct 391 ms 61632 KB Output is correct
18 Correct 380 ms 54232 KB Output is correct
19 Correct 387 ms 61336 KB Output is correct
20 Correct 329 ms 111288 KB Output is correct
21 Correct 351 ms 110436 KB Output is correct
22 Correct 613 ms 42856 KB Output is correct
23 Correct 698 ms 42700 KB Output is correct
24 Correct 679 ms 42188 KB Output is correct
25 Correct 713 ms 59532 KB Output is correct
26 Correct 477 ms 49140 KB Output is correct
27 Correct 482 ms 45948 KB Output is correct
28 Correct 492 ms 44232 KB Output is correct
29 Correct 364 ms 111356 KB Output is correct
30 Correct 323 ms 110512 KB Output is correct
31 Correct 73 ms 30088 KB Output is correct
32 Correct 381 ms 110632 KB Output is correct