oj.uz

Submission #250875

# Submission time Handle Problem Language Result Execution time Memory
250875 2020-07-19T10:35:37 Z VEGAnn Zagrade (COI17_zagrade) C++14
40 / 100
 3000 ms 44616 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;
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[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)
        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 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7552 KB Output is correct
4 Correct 5 ms 7552 KB Output is correct
5 Correct 5 ms 7552 KB Output is correct
6 Correct 6 ms 7552 KB Output is correct
7 Correct 5 ms 7552 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 7 ms 7552 KB Output is correct
10 Correct 6 ms 7552 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 44428 KB Output is correct
2 Correct 499 ms 44616 KB Output is correct
3 Correct 455 ms 44428 KB Output is correct
4 Correct 511 ms 44428 KB Output is correct
5 Correct 482 ms 44552 KB Output is correct
6 Correct 496 ms 44424 KB Output is correct
7 Correct 459 ms 44428 KB Output is correct
8 Correct 488 ms 44556 KB Output is correct
9 Correct 482 ms 44300 KB Output is correct
10 Correct 452 ms 44384 KB Output is correct
11 Correct 458 ms 44352 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7552 KB Output is correct
4 Correct 5 ms 7552 KB Output is correct
5 Correct 5 ms 7552 KB Output is correct
6 Correct 6 ms 7552 KB Output is correct
7 Correct 5 ms 7552 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 7 ms 7552 KB Output is correct
10 Correct 6 ms 7552 KB Output is correct
11 Correct 458 ms 44428 KB Output is correct
12 Correct 499 ms 44616 KB Output is correct
13 Correct 455 ms 44428 KB Output is correct
14 Correct 511 ms 44428 KB Output is correct
15 Correct 482 ms 44552 KB Output is correct
16 Correct 496 ms 44424 KB Output is correct
17 Correct 459 ms 44428 KB Output is correct
18 Correct 488 ms 44556 KB Output is correct
19 Correct 482 ms 44300 KB Output is correct
20 Correct 452 ms 44384 KB Output is correct
21 Correct 458 ms 44352 KB Output is correct
22 Correct 1214 ms 26072 KB Output is correct
23 Correct 1197 ms 25920 KB Output is correct
24 Correct 1149 ms 25868 KB Output is correct
25 Correct 1192 ms 25868 KB Output is correct
26 Correct 599 ms 31980 KB Output is correct
27 Correct 636 ms 29196 KB Output is correct
28 Correct 617 ms 28040 KB Output is correct
29 Correct 448 ms 44412 KB Output is correct
30 Correct 484 ms 44424 KB Output is correct
31 Execution timed out 3069 ms 27020 KB Time limit exceeded
32 Halted 0 ms 0 KB -