Submission #699270

#	Time	Username	Problem	Language	Result	Execution time	Memory
699270		BERNARB01	Zagrade (COI17_zagrade)	C++17	0 / 100	297 ms	46980 KiB

zagrade

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 3e5 + 9;

string a;
vector<int> g[N];
int vis[N], sbt[N], cnt[N];
long long ans = 0;

inline int fcd(int v, int pr, int n) {
  for (int u : g[v]) {
    if (u != pr && !vis[u] && sbt[u] > n) {
      return fcd(u, v, n);
    }
  }
  return v;
}

void dfs0(int v, int pr) {
  sbt[v] = 1;
  for (int u : g[v]) {
    if (u != pr && !vis[u]) {
      dfs0(u, v);
      sbt[v] += sbt[u];
    }
  }
}

void dfsq(int v, int pr, int mn, int s) {
  s += (a[v] == '(' ? 1 : -1);
  mn = min(mn, s);
  ans += cnt[-mn - min(0, s)];
  if (mn >= 0 && s == 0) {
    ans++;
  }
  for (int u : g[v]) {
    if (u != pr && !vis[u]) {
      dfsq(u, v, mn, s);
    }
  }
}

void dfsu(int v, int pr, int mn, int s, int d) {
  s += (a[v] == '(' ? 1 : -1);
  mn = min(mn + (a[v] == '(' ? 1 : -1), 0);
  if (mn == 0) {
    cnt[s] += d;
  }
  for (int u : g[v]) {
    if (u != pr && !vis[u]) {
      dfsu(u, v, mn, s, d);
    }
  }
}

void solve(int v) {
  vis[v] = 1;
  for (int u : g[v]) {
    if (vis[u]) {
      continue;
    }
    dfsq(u, v, min((a[v] == '(' ? 1 : -1), 0), (a[v] == '(' ? 1 : -1));
    dfsu(u, v, min((a[v] == '(' ? 1 : -1), 0), (a[v] == '(' ? 1 : -1), 1);
  }
  for (int u : g[v]) {
    if (vis[u]) {
      continue;
    }
    dfsu(u, v, min((a[v] == '(' ? 1 : -1), 0), (a[v] == '(' ? 1 : -1), -1);
  }
  for (int u : g[v]) {
    if (vis[u]) {
      continue;
    }
    int cd = fcd(u, -1, sbt[u] >> 1);
    dfs0(cd, -1);
    solve(cd);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  cin >> a;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs0(0, -1);
  int cd = fcd(0, -1, n >> 1);
  dfs0(cd, -1);
  solve(cd);
  cout << ans << '\n';
  return 0;
}

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