oj.uz

Submission #480307

# Submission time Handle Problem Language Result Execution time Memory
480307 2021-10-15T15:20:11 Z BERNARB01 Zagrade (COI17_zagrade) C++17
40 / 100
 153 ms 24376 KB 
#include <bits/stdc++.h>

using namespace std;

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

int n;
string a;
vector<int> g[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> a;
  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);
  }
  if (n <= 1000) {
    function<int(int, int, int)> DFS = [&](int v, int pr, int bal) {
      bal += (a[v] == '(') - (a[v] == ')');
      if (bal < 0) {
        return 0;
      }
      int ret = !bal;
      for (int u : g[v]) {
        if (u == pr) {
          continue;
        }
        ret += DFS(u, v, bal);
      }
      return ret;
    };
    int ans = 0;
    for (int i = 0; i < n; i++) {
      ans += DFS(i, -1, 0);
    }
    cout << ans << '\n';
  } else {
    long long ans = 0;
    for (int itr = 0; itr < 2; itr++) {
      reverse(a.begin(), a.end());
      vector<pair<char, int>> stk;
      for (int i = 0; i < n; i++) {
        if (a[i] == ')') {
          while (!stk.empty() && stk.back().first == ')') {
            stk.pop_back();
          }
          if (stk.empty()) {
            continue;
          }
          stk.back().first = ')';
          stk.back().second += 1;
          ans += stk.back().second;
        } else {
          if (stk.empty()) {
            stk.push_back({'(', 0});
            continue;
          }
          if (stk.back().first == '(') {
            stk.push_back({'(', 0});
            continue;
          }
          stk.push_back({'(', stk.back().second});
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7372 KB Output is correct
2 Correct 14 ms 7392 KB Output is correct
3 Correct 12 ms 7372 KB Output is correct
4 Correct 7 ms 7372 KB Output is correct
5 Correct 9 ms 7372 KB Output is correct
6 Correct 13 ms 7332 KB Output is correct
7 Correct 11 ms 7392 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 9 ms 7372 KB Output is correct
10 Correct 8 ms 7396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 17032 KB Output is correct
2 Correct 93 ms 21180 KB Output is correct
3 Correct 100 ms 21204 KB Output is correct
4 Correct 87 ms 21160 KB Output is correct
5 Correct 98 ms 21212 KB Output is correct
6 Correct 98 ms 22752 KB Output is correct
7 Correct 87 ms 21172 KB Output is correct
8 Correct 96 ms 22924 KB Output is correct
9 Correct 89 ms 21276 KB Output is correct
10 Correct 90 ms 24376 KB Output is correct
11 Correct 89 ms 24340 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7372 KB Output is correct
2 Correct 14 ms 7392 KB Output is correct
3 Correct 12 ms 7372 KB Output is correct
4 Correct 7 ms 7372 KB Output is correct
5 Correct 9 ms 7372 KB Output is correct
6 Correct 13 ms 7332 KB Output is correct
7 Correct 11 ms 7392 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 9 ms 7372 KB Output is correct
10 Correct 8 ms 7396 KB Output is correct
11 Correct 100 ms 17032 KB Output is correct
12 Correct 93 ms 21180 KB Output is correct
13 Correct 100 ms 21204 KB Output is correct
14 Correct 87 ms 21160 KB Output is correct
15 Correct 98 ms 21212 KB Output is correct
16 Correct 98 ms 22752 KB Output is correct
17 Correct 87 ms 21172 KB Output is correct
18 Correct 96 ms 22924 KB Output is correct
19 Correct 89 ms 21276 KB Output is correct
20 Correct 90 ms 24376 KB Output is correct
21 Correct 89 ms 24340 KB Output is correct
22 Incorrect 153 ms 22384 KB Output isn't correct
23 Halted 0 ms 0 KB -