oj.uz

Submission #250882

# Submission time Handle Problem Language Result Execution time Memory
250882 2020-07-19T10:45:48 Z VEGAnn Zagrade (COI17_zagrade) C++14
100 / 100
 1375 ms 45260 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int N = 300100;
vector<int> g[N];
ll ans;
int n, siz[N], ad[N], sta[N], ed[N], mn_sta[N], mn_ed[N], mem[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[u]) 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[u]) 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)
        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 SZ = siz[v];
    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

    fill(mem, mem + SZ + 1, 0);

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

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

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

    //right

    fill(mem, mem + SZ + 1, 0);

    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 5 ms 7552 KB Output is correct
2 Correct 5 ms 7552 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7552 KB Output is correct
5 Correct 5 ms 7552 KB Output is correct
6 Correct 5 ms 7552 KB Output is correct
7 Correct 5 ms 7552 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7552 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 44488 KB Output is correct
2 Correct 481 ms 44428 KB Output is correct
3 Correct 462 ms 44476 KB Output is correct
4 Correct 476 ms 44428 KB Output is correct
5 Correct 452 ms 44556 KB Output is correct
6 Correct 450 ms 44428 KB Output is correct
7 Correct 493 ms 44316 KB Output is correct
8 Correct 460 ms 44428 KB Output is correct
9 Correct 471 ms 44424 KB Output is correct
10 Correct 458 ms 44684 KB Output is correct
11 Correct 456 ms 44428 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7552 KB Output is correct
2 Correct 5 ms 7552 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7552 KB Output is correct
5 Correct 5 ms 7552 KB Output is correct
6 Correct 5 ms 7552 KB Output is correct
7 Correct 5 ms 7552 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7552 KB Output is correct
11 Correct 465 ms 44488 KB Output is correct
12 Correct 481 ms 44428 KB Output is correct
13 Correct 462 ms 44476 KB Output is correct
14 Correct 476 ms 44428 KB Output is correct
15 Correct 452 ms 44556 KB Output is correct
16 Correct 450 ms 44428 KB Output is correct
17 Correct 493 ms 44316 KB Output is correct
18 Correct 460 ms 44428 KB Output is correct
19 Correct 471 ms 44424 KB Output is correct
20 Correct 458 ms 44684 KB Output is correct
21 Correct 456 ms 44428 KB Output is correct
22 Correct 1297 ms 26124 KB Output is correct
23 Correct 1304 ms 25868 KB Output is correct
24 Correct 1375 ms 25924 KB Output is correct
25 Correct 1303 ms 25980 KB Output is correct
26 Correct 600 ms 31888 KB Output is correct
27 Correct 623 ms 29208 KB Output is correct
28 Correct 639 ms 28040 KB Output is correct
29 Correct 453 ms 44380 KB Output is correct
30 Correct 451 ms 44328 KB Output is correct
31 Correct 115 ms 26804 KB Output is correct
32 Correct 509 ms 45260 KB Output is correct