Submission #549674

#	Time	Username	Problem	Language	Result	Execution time	Memory
549674		Yazan_Alattar	Zagrade (COI17_zagrade)	C++14	0 / 100	5 ms	5552 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

map <int,int> cnt[2];
vector <int> adj[M], v[M];
int n, c[M], pref[M], sz[M], ans, dep[M], mn[M][20], anc[M][0];

void calc(int node, int p){
    sz[node] = 1;

    for(auto i : adj[node]) if(i != p){
        pref[i] = pref[node] + c[i];
        dep[i] = dep[node] + 1;
        mn[i][0] = pref[node];
        anc[i][0] = node;

        calc(i, node);
        sz[node] += sz[i];
    }
    return;
}

int get(int a, int b){
    int ret = pref[a];

    for(int i = 17; i >= 0; --i) if(dep[anc[a][i]] >= dep[b]){
        ret = min(ret, mn[a][i]);
        a = anc[a][i];
    }
    return ret;
}

void dfs(int node, int p, bool keep){
    int big = 0;
    for(auto i : adj[node]) if(i != p && sz[i] > sz[big]) big = i;
    for(auto i : adj[node]) if(i != p && i != big) dfs(i, node, 0);

    if(big){
        dfs(big, node, 1);
        swap(v[node], v[big]);
    }
    v[node].pb(node);

    for(auto i : adj[node]) if(i != p && i != big){
        for(auto j : v[i]){
            int mn = get(j, node);

            if(mn - pref[node] + c[node] >= 0) ans += cnt[1][-(pref[j] - pref[node] + c[node])];
            if(pref[j] - pref[node] <= 0) ans += cnt[0][-(pref[j] - pref[node])];
        }
        for(auto j : v[i]){
            int mn = get(j, node);

            if(mn - pref[node] + c[node] >= 0) ++cnt[0][pref[j] - pref[node] + c[node]];
            if(pref[j] - pref[node] <= 0) ++cnt[1][pref[j] - pref[node]];
        }

        for(auto j : v[i]) v[node].pb(j);
    }

    if(!keep){
        for(auto i : v[node]){
            cnt[0][pref[i] - pref[node] + c[node]] = 0;
            cnt[1][pref[i] - pref[node]] = 0;
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i){
        char x; cin >> x;
        c[i] = (x == '(' ? 1 : -1);
    }
    for(int i = 1; i < n; ++i){
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    dep[1] = 1;
    calc(1, 0);
    for(int j = 1; j < 18; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1], mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);

    dfs(1, 0, 1);
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'void calc(int, int)':
zagrade.cpp:29:17: warning: array subscript 0 is outside array bounds of 'int [0]' [-Warray-bounds]
   29 |         anc[i][0] = node;
      |         ~~~~~~~~^
zagrade.cpp: In function 'int get(int, int)':
zagrade.cpp:40:49: warning: array subscript i is outside array bounds of 'int [0]' [-Warray-bounds]
   40 |     for(int i = 17; i >= 0; --i) if(dep[anc[a][i]] >= dep[b]){
      |                                         ~~~~~~~~^
zagrade.cpp: In function 'int main()':
zagrade.cpp:101:89: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
  101 |     for(int j = 1; j < 18; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1], mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);
      |                                                                             ~~~~~~~~~~~~^
zagrade.cpp:101:97: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
  101 |     for(int j = 1; j < 18; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1], mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);
      |                                                                         ~~~~~~~~~~~~~~~~~~~~~~~~^
zagrade.cpp:101:69: warning: array subscript j is outside array bounds of 'int [0]' [-Warray-bounds]
  101 |     for(int j = 1; j < 18; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1], mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);
      |                                                             ~~~~~~~~^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60