oj.uz

Submission #250877

# Submission time Handle Problem Language Result Execution time Memory
250877 2020-07-19T10:39:45 Z VEGAnn Zagrade (COI17_zagrade) C++14
40 / 100
 3000 ms 37644 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[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 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7552 KB Output is correct
5 Correct 6 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 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 434 ms 37388 KB Output is correct
2 Correct 471 ms 37388 KB Output is correct
3 Correct 432 ms 37516 KB Output is correct
4 Correct 442 ms 37256 KB Output is correct
5 Correct 467 ms 37260 KB Output is correct
6 Correct 426 ms 37644 KB Output is correct
7 Correct 420 ms 37384 KB Output is correct
8 Correct 437 ms 37516 KB Output is correct
9 Correct 453 ms 37388 KB Output is correct
10 Correct 409 ms 37560 KB Output is correct
11 Correct 398 ms 37260 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 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7552 KB Output is correct
5 Correct 6 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 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 434 ms 37388 KB Output is correct
12 Correct 471 ms 37388 KB Output is correct
13 Correct 432 ms 37516 KB Output is correct
14 Correct 442 ms 37256 KB Output is correct
15 Correct 467 ms 37260 KB Output is correct
16 Correct 426 ms 37644 KB Output is correct
17 Correct 420 ms 37384 KB Output is correct
18 Correct 437 ms 37516 KB Output is correct
19 Correct 453 ms 37388 KB Output is correct
20 Correct 409 ms 37560 KB Output is correct
21 Correct 398 ms 37260 KB Output is correct
22 Correct 1364 ms 25868 KB Output is correct
23 Correct 1088 ms 25868 KB Output is correct
24 Correct 1172 ms 26040 KB Output is correct
25 Correct 1246 ms 25868 KB Output is correct
26 Correct 652 ms 29580 KB Output is correct
27 Correct 641 ms 27788 KB Output is correct
28 Correct 722 ms 27148 KB Output is correct
29 Correct 430 ms 37284 KB Output is correct
30 Correct 421 ms 37476 KB Output is correct
31 Execution timed out 3051 ms 26828 KB Time limit exceeded
32 Halted 0 ms 0 KB -