oj.uz

Submission #250873

# Submission time Handle Problem Language Result Execution time Memory
250873 2020-07-19T10:33:04 Z VEGAnn Zagrade (COI17_zagrade) C++14
40 / 100
 3000 ms 53088 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 300100;
gp_hash_table<int, int> mem;
vector<int> g[N];
ll ans;
int n, siz[N], ad[N], sta[N], ed[N], mn_sta[N], mn_ed[N];
bool used[N];
string s;

void build_sz(int v, int p){
    siz[v] = 1;

    for (int u : g[v]){
        if (u == p || used[v]) continue;

        build_sz(u, v);

        siz[v] += siz[u];
    }
}

int search(int v, int pr, int SZ){
    for (int u : g[v]){
        if (u == pr || used[v]) continue;

        if (siz[u] > SZ / 2)
            return search(u, v, SZ);
    }

    return v;
}

void dfs(int v, int pr){
    mn_sta[v] = min(mn_sta[pr] + ad[v], 0);
    mn_ed[v] = min(mn_ed[pr] - ad[v], 0);

    sta[v] = sta[pr] + ad[v];
    ed[v] = ed[pr] + ad[v];

    for (int u : g[v]){
        if (used[u] || u == pr) continue;

        dfs(u, v);
    }
}

void calc(int v, int pr){
    if (mn_sta[v] == 0 && mem.find(-sta[v]) != mem.end())
        ans += mem[-sta[v]];

    for (int u : g[v]){
        if (used[u] || u == pr) continue;

        calc(u, v);
    }
}

void upda(int v, int pr){
    if (mn_ed[v] == 0)
        mem[ed[v]]++;

    for (int u : g[v]){
        if (used[u] || u == pr) continue;

        upda(u, v);
    }
}

void build_cd(int v){
    build_sz(v, -1);

    int cen = search(v, -1, siz[v]);

    used[cen] = 1;

    // calc subtree sums

    sta[cen] = 0;
    ed[cen] = ad[cen];

    mn_ed[cen] = min(0, -ad[cen]);
    mn_sta[cen] = 0;

    for (int u : g[cen]){
        if (used[u]) continue;

        dfs(u, cen);
    }

    // update ans (left, right)

    //left

    mem.clear();

    if (mn_ed[cen] == 0)
        mem[ed[cen]]++;

    for (int u : g[cen]){
        if (used[u]) continue;

        calc(u, cen);
        upda(u, cen);
    }

    //right

    mem.clear();

    reverse(all(g[cen]));

    for (int u : g[cen]){
        if (used[u]) continue;

        calc(u, cen);
        upda(u, cen);
    }

    if (mn_sta[cen] == 0)
        ans += mem[-sta[cen]];

    // continue process in children subtrees

    for (int u : g[cen])
        if (!used[u])
            build_cd(u);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> s;

    for (int i = 0; i < n; i++){
        if (s[i] == '(')
            ad[i] = 1;
        else ad[i] = -1;
    }

    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        x--; y--;

        g[x].PB(y);
        g[y].PB(x);
    }

    build_cd(0);

    cout << ans;

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 43276 KB Output is correct
2 Correct 658 ms 45560 KB Output is correct
3 Correct 554 ms 43276 KB Output is correct
4 Correct 614 ms 46076 KB Output is correct
5 Correct 539 ms 43936 KB Output is correct
6 Correct 553 ms 43788 KB Output is correct
7 Correct 536 ms 43784 KB Output is correct
8 Correct 559 ms 43696 KB Output is correct
9 Correct 547 ms 43788 KB Output is correct
10 Correct 584 ms 52904 KB Output is correct
11 Correct 489 ms 43660 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7552 KB Output is correct
2 Correct 6 ms 7552 KB Output is correct
3 Correct 6 ms 7552 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 6 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 6 ms 7424 KB Output is correct
11 Correct 572 ms 43276 KB Output is correct
12 Correct 658 ms 45560 KB Output is correct
13 Correct 554 ms 43276 KB Output is correct
14 Correct 614 ms 46076 KB Output is correct
15 Correct 539 ms 43936 KB Output is correct
16 Correct 553 ms 43788 KB Output is correct
17 Correct 536 ms 43784 KB Output is correct
18 Correct 559 ms 43696 KB Output is correct
19 Correct 547 ms 43788 KB Output is correct
20 Correct 584 ms 52904 KB Output is correct
21 Correct 489 ms 43660 KB Output is correct
22 Correct 1289 ms 25280 KB Output is correct
23 Correct 1256 ms 25232 KB Output is correct
24 Correct 1232 ms 25232 KB Output is correct
25 Correct 1384 ms 25356 KB Output is correct
26 Correct 681 ms 31244 KB Output is correct
27 Correct 688 ms 28428 KB Output is correct
28 Correct 701 ms 27336 KB Output is correct
29 Correct 582 ms 53088 KB Output is correct
30 Correct 588 ms 52960 KB Output is correct
31 Execution timed out 3058 ms 26116 KB Time limit exceeded
32 Halted 0 ms 0 KB -