oj.uz

Submission #250876

# Submission time Handle Problem Language Result Execution time Memory
250876 2020-07-19T10:36:39 Z VEGAnn Zagrade (COI17_zagrade) C++14
40 / 100
 3000 ms 44428 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 7552 KB Output is correct
2 Correct 6 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 8 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 5 ms 7424 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 491 ms 44300 KB Output is correct
2 Correct 517 ms 44304 KB Output is correct
3 Correct 484 ms 44428 KB Output is correct
4 Correct 515 ms 44428 KB Output is correct
5 Correct 489 ms 44428 KB Output is correct
6 Correct 496 ms 44428 KB Output is correct
7 Correct 490 ms 44428 KB Output is correct
8 Correct 486 ms 44416 KB Output is correct
9 Correct 470 ms 44428 KB Output is correct
10 Correct 446 ms 44348 KB Output is correct
11 Correct 453 ms 44428 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7552 KB Output is correct
2 Correct 6 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 8 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 5 ms 7424 KB Output is correct
10 Correct 6 ms 7552 KB Output is correct
11 Correct 491 ms 44300 KB Output is correct
12 Correct 517 ms 44304 KB Output is correct
13 Correct 484 ms 44428 KB Output is correct
14 Correct 515 ms 44428 KB Output is correct
15 Correct 489 ms 44428 KB Output is correct
16 Correct 496 ms 44428 KB Output is correct
17 Correct 490 ms 44428 KB Output is correct
18 Correct 486 ms 44416 KB Output is correct
19 Correct 470 ms 44428 KB Output is correct
20 Correct 446 ms 44348 KB Output is correct
21 Correct 453 ms 44428 KB Output is correct
22 Correct 1227 ms 26020 KB Output is correct
23 Correct 1329 ms 25868 KB Output is correct
24 Correct 1299 ms 25996 KB Output is correct
25 Correct 1529 ms 25992 KB Output is correct
26 Correct 610 ms 31936 KB Output is correct
27 Correct 597 ms 29140 KB Output is correct
28 Correct 657 ms 28040 KB Output is correct
29 Correct 463 ms 44300 KB Output is correct
30 Correct 466 ms 44428 KB Output is correct
31 Execution timed out 3099 ms 26648 KB Time limit exceeded
32 Halted 0 ms 0 KB -