Submission #1081487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081487		juicy	Zagrade (COI17_zagrade)	C++17	100 / 100	467 ms	55956 KiB

zagrade

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 3e5 + 5;
 
int n;
int sz[N], x[N], y[N], f[N], b[N], mx[N], mn[N], dep[N];
bool del[N];
long long res;
string s;
vector<int> g[N];
 
void dfs(int u, int p) {
  sz[u] = 1;
  for (int v : g[u]) {
    if (!del[v] && v != p) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}
 
int findCen(int u, int p, int tot) {
  for (int v : g[u]) {
    if (!del[v] && v != p && sz[v] * 2 > tot) {
      return findCen(v, u, tot);
    }
  }
  return u;
}
 
vector<int> ver;
 
void DFS(int u, int p) {
  x[u] = x[p] + (s[u] == '(' ? 1 : -1);
  y[u] = y[p] + (s[u] == '(' ? 1 : -1);
  mx[u] = max(mx[p], x[u]);
  mn[u] = min(mn[p], y[u]);
  dep[u] = dep[p] + 1;
  ver.push_back(u);
  for (int v : g[u]) {
    if (!del[v] && v != p) {
      DFS(v, u);
    }
  }
}
 
void cd(int u) {
  dfs(u, u);
  u = findCen(u, u, sz[u]);
  del[u] = 1;
  dep[u] = 1;
  ++b[0];
  f[1] += s[u] == '(';
  mn[u] = mx[u] = y[u] = 0;
  x[u] = s[u] == '(' ? 1 : -1;
  mx[u] = max(mx[u], x[u]);
  int d = 1;
  for (int v : g[u]) {
    if (!del[v]) {
      vector<int>().swap(ver);
      DFS(v, u);
      for (int c : ver) {
        d = max(d, dep[c]);
        if (y[c] <= mn[c]) {
          res += f[-y[c]];
        }
        if (x[c] >= mx[c]) {
          res += b[x[c]];
        }
      }
      for (int c : ver) {
        if (y[c] <= mn[c]) {
          ++b[-y[c]];
        }
        if (x[c] >= mx[c]) {
          ++f[x[c]];
        }
      }
    }
  }
  for (int i = 0; i <= d; ++i) {
    f[i] = b[i] = 0;
  }
  for (int v : g[u]) {
    if (!del[v]) {
      cd(v);
    }
  }
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n >> s;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v; --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  cd(0);
  cout << res;
  return 0;
}

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