oj.uz

Submission #586772

# Submission time Handle Problem Language Result Execution time Memory
586772 2022-06-30T16:54:08 Z MilosMilutinovic Zagrade (COI17_zagrade) C++14
100 / 100
 1052 ms 57668 KB 
/**
 *    author:  wxhtzdy
 *    created: 30.06.2022 10:05:38
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<vector<int>> g(n);
  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);
  }
  vector<bool> was(n);
  vector<int> sz(n);
  function<void(int, int)> Dfs = [&](int v, int pr) {
    sz[v] = 1;
    for (int u : g[v]) {
      if (u == pr || was[u]) {
        continue;
      }
      Dfs(u, v);
      sz[v] += sz[u];
    }
  };
  function<int(int, int, int)> Find = [&](int v, int pr, int n) {
    for (int u : g[v]) {
      if (u == pr || was[u] || sz[u] * 2 < n) {
        continue;
      }
      return Find(u, v, n);
    }
    return v;
  };
  map<int, int> cnt;
  long long ans = 0;
  function<void(int, int, int, int, int)> Go = [&](int v, int pr, int bal, int mn, int f) {
    int me = (s[v] == '(' ? 1 : -1);
    bal += me;
    mn = min(me, me + mn);
    if (mn >= 0) {
      cnt[bal] += f;
    }
    for (int u : g[v]) {
      if (u == pr || was[u]) {
        continue;
      }
      Go(u, v, bal, mn, f);
    }
  };
  function<void(int, int, int, int)> Run = [&](int v, int pr, int bal, int mn) {
    bal += (s[v] == '(' ? +1 : -1);
    mn = min(mn, bal);
    if (mn == 0 && bal == 0) {
      ans += 1;
    }
    if (-bal + mn >= 0) {
      ans += cnt[-bal];      
    }
    for (int u : g[v]) {
      if (u == pr || was[u]) {
        continue;
      }
      Run(u, v, bal, mn);
    }
  };          
  function<void(int)> Solve = [&](int v) {
    Dfs(v, v);
    v = Find(v, v, sz[v]);
    was[v] = true;
    cnt.clear();
    for (int u : g[v]) { 
      if (was[u]) {
        continue;
      }
      Go(u, v, 0, 1, +1);     
    }       
    if (s[v] == ')') {
      ans += cnt[1];
    }     
    for (int u : g[v]) {
      if (was[u]) {
        continue;
      }
      int me = (s[v] == '(' ? +1 : -1);
      Go(u, v, 0, 1, -1);
      Run(u, v, me, me);
      Go(u, v, 0, 1, +1);     
    }
    for (int u : g[v]) {
      if (!was[u]) {
        Solve(u);
      }
    }
  };
  Solve(0);
  cout << ans << '\n';                    
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 50652 KB Output is correct
2 Correct 779 ms 53360 KB Output is correct
3 Correct 628 ms 50676 KB Output is correct
4 Correct 688 ms 52752 KB Output is correct
5 Correct 629 ms 50676 KB Output is correct
6 Correct 699 ms 51616 KB Output is correct
7 Correct 666 ms 50736 KB Output is correct
8 Correct 761 ms 51528 KB Output is correct
9 Correct 635 ms 50528 KB Output is correct
10 Correct 1006 ms 57668 KB Output is correct
11 Correct 513 ms 50624 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 612 ms 50652 KB Output is correct
12 Correct 779 ms 53360 KB Output is correct
13 Correct 628 ms 50676 KB Output is correct
14 Correct 688 ms 52752 KB Output is correct
15 Correct 629 ms 50676 KB Output is correct
16 Correct 699 ms 51616 KB Output is correct
17 Correct 666 ms 50736 KB Output is correct
18 Correct 761 ms 51528 KB Output is correct
19 Correct 635 ms 50528 KB Output is correct
20 Correct 1006 ms 57668 KB Output is correct
21 Correct 513 ms 50624 KB Output is correct
22 Correct 1052 ms 22632 KB Output is correct
23 Correct 945 ms 22632 KB Output is correct
24 Correct 986 ms 22632 KB Output is correct
25 Correct 1014 ms 22640 KB Output is correct
26 Correct 720 ms 31840 KB Output is correct
27 Correct 709 ms 27688 KB Output is correct
28 Correct 692 ms 26056 KB Output is correct
29 Correct 1027 ms 57668 KB Output is correct
30 Correct 952 ms 57668 KB Output is correct
31 Correct 103 ms 22276 KB Output is correct
32 Correct 499 ms 50624 KB Output is correct