Submission #250879

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250879	2020-07-19T10:42:53 Z	VEGAnn	Zagrade (COI17_zagrade)	C++14	Compilation error	0 ms	0 KB

zagrade

#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 it = 0; it < sz(g[v]); it++)
        int u = g[v][it];

        if (used[u]) {
            swap(g[v].back(), g[v][it]);
            g[v].pop_back();
            it--;
            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;
}

Compilation message

zagrade.cpp: In function 'void build_cd(int)':
zagrade.cpp:93:27: error: 'sz' was not declared in this scope
     for (int it = 0; it < sz(g[v]); it++)
                           ^~
zagrade.cpp:93:27: note: suggested alternative: 's'
     for (int it = 0; it < sz(g[v]); it++)
                           ^~
                           s
zagrade.cpp:93:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int it = 0; it < sz(g[v]); it++)
     ^~~
zagrade.cpp:96:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         if (used[u]) {
         ^~
zagrade.cpp:94:13: warning: unused variable 'u' [-Wunused-variable]
         int u = g[v][it];
             ^
zagrade.cpp:96:18: error: 'u' was not declared in this scope
         if (used[u]) {
                  ^
zagrade.cpp:97:36: error: 'it' was not declared in this scope
             swap(g[v].back(), g[v][it]);
                                    ^~
zagrade.cpp:97:36: note: suggested alternative: 'int'
             swap(g[v].back(), g[v][it]);
                                    ^~
                                    int
zagrade.cpp:100:13: error: continue statement not within a loop
             continue;
             ^~~~~~~~
zagrade.cpp:103:13: error: 'u' was not declared in this scope
         dfs(u, cen);
             ^
zagrade.cpp:80:9: warning: unused variable 'SZ' [-Wunused-variable]
     int SZ = siz[v];
         ^~
zagrade.cpp: At global scope:
zagrade.cpp:110:9: error: expected constructor, destructor, or type conversion before '(' token
     fill(mem, mem + SZ + 1, 0);
         ^
zagrade.cpp:112:5: error: expected unqualified-id before 'if'
     if (mn_ed[cen] == 0)
     ^~
zagrade.cpp:115:5: error: expected unqualified-id before 'for'
     for (int u : g[cen]){
     ^~~
zagrade.cpp:124:9: error: expected constructor, destructor, or type conversion before '(' token
     fill(mem, mem + SZ + 1, 0);
         ^
zagrade.cpp:126:12: error: expected constructor, destructor, or type conversion before '(' token
     reverse(all(g[cen]));
            ^
zagrade.cpp:128:5: error: expected unqualified-id before 'for'
     for (int u : g[cen]){
     ^~~
zagrade.cpp:135:5: error: expected unqualified-id before 'if'
     if (mn_sta[cen] == 0)
     ^~
zagrade.cpp:140:5: error: expected unqualified-id before 'for'
     for (int u : g[cen])
     ^~~
zagrade.cpp:143:1: error: expected declaration before '}' token
 }
 ^