oj.uz

Submission #250881

# Submission time Handle Problem Language Result Execution time Memory
250881 2020-07-19T10:45:00 Z VEGAnn Zagrade (COI17_zagrade) C++14
40 / 100
 3000 ms 44960 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[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[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 6 ms 7552 KB Output is correct
2 Correct 5 ms 7552 KB Output is correct
3 Correct 13 ms 7552 KB Output is correct
4 Correct 6 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 5 ms 7552 KB Output is correct
9 Correct 5 ms 7552 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 464 ms 44552 KB Output is correct
2 Correct 492 ms 44940 KB Output is correct
3 Correct 461 ms 44940 KB Output is correct
4 Correct 488 ms 44812 KB Output is correct
5 Correct 466 ms 44808 KB Output is correct
6 Correct 464 ms 44812 KB Output is correct
7 Correct 474 ms 44812 KB Output is correct
8 Correct 472 ms 44812 KB Output is correct
9 Correct 465 ms 44812 KB Output is correct
10 Correct 460 ms 44808 KB Output is correct
11 Correct 458 ms 44812 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 5 ms 7552 KB Output is correct
3 Correct 13 ms 7552 KB Output is correct
4 Correct 6 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 5 ms 7552 KB Output is correct
9 Correct 5 ms 7552 KB Output is correct
10 Correct 5 ms 7552 KB Output is correct
11 Correct 464 ms 44552 KB Output is correct
12 Correct 492 ms 44940 KB Output is correct
13 Correct 461 ms 44940 KB Output is correct
14 Correct 488 ms 44812 KB Output is correct
15 Correct 466 ms 44808 KB Output is correct
16 Correct 464 ms 44812 KB Output is correct
17 Correct 474 ms 44812 KB Output is correct
18 Correct 472 ms 44812 KB Output is correct
19 Correct 465 ms 44812 KB Output is correct
20 Correct 460 ms 44808 KB Output is correct
21 Correct 458 ms 44812 KB Output is correct
22 Correct 1199 ms 26316 KB Output is correct
23 Correct 1172 ms 26504 KB Output is correct
24 Correct 1231 ms 26256 KB Output is correct
25 Correct 1292 ms 26328 KB Output is correct
26 Correct 617 ms 32204 KB Output is correct
27 Correct 626 ms 29468 KB Output is correct
28 Correct 646 ms 28608 KB Output is correct
29 Correct 452 ms 44808 KB Output is correct
30 Correct 463 ms 44960 KB Output is correct
31 Execution timed out 3088 ms 27012 KB Time limit exceeded
32 Halted 0 ms 0 KB -