oj.uz

Submission #1081476

# Submission time Handle Problem Language Result Execution time Memory
1081476 2024-08-30T05:37:39 Z juicy Zagrade (COI17_zagrade) C++17
10 / 100
 3000 ms 54576 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e5;

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]);
  ver.push_back(u);
  for (int v : g[u]) {
    if (!del[v] && v != p) {
      dep[v] = dep[u] + 1;
      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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7384 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Correct 4 ms 7428 KB Output is correct
5 Correct 4 ms 7528 KB Output is correct
6 Correct 4 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 4 ms 7516 KB Output is correct
9 Correct 6 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 54576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7384 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Correct 4 ms 7428 KB Output is correct
5 Correct 4 ms 7528 KB Output is correct
6 Correct 4 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 4 ms 7516 KB Output is correct
9 Correct 6 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Execution timed out 3054 ms 54576 KB Time limit exceeded
12 Halted 0 ms 0 KB -