oj.uz

Submission #144393

# Submission time Handle Problem Language Result Execution time Memory
144393 2019-08-16T19:30:04 Z Milki Zagrade (COI17_zagrade) C++14
100 / 100
 1599 ms 51216 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 3e5 + 5;

int n, sz[MAXN];
string s;
vector <int> E[MAXN];
bool bio[MAXN];
ll sol;

void dfs_sz(int x, int p = -1){
  sz[x] = 1;
  for(auto e : E[x]){
    if(bio[e] || e == p) continue;
    dfs_sz(e, x);
    sz[x] += sz[e];
  }
}

void find_centroid(int x, int total, int &centroid, int p = -1){
  int mx = 0;
  for(auto e : E[x]){
    if(bio[e] || e == p) continue;
    find_centroid(e, total, centroid, x);
    mx = max(mx, sz[e]);
  }

  if(max(mx, total - sz[x]) <= total / 2){
    centroid = x;
  }
}

void dfs_left(int x, vector <int> &v, int add, int sum = 0, int mx = 0, int p = -1){
  if(s[x] == '(') sum --, mx --;
  else sum ++, mx ++;

  mx = max(mx, 0);

  if(mx <= 0 && sum <= 0){
    v[-sum] += add;
  }

  for(auto e : E[x]){
    if(bio[e] || e == p) continue;
    dfs_left(e, v, add, sum, mx, x);
  }
}

void dfs_right(int x, vector <int> &v, int add, int sum = 0, int mn = 0, int p = -1){
  if(s[x] == '(') sum --, mn --;
  else sum ++, mn ++;

  mn = min(mn, 0);

  if(mn >= 0 && sum >= 0){
    v[sum] += add;
  }

  for(auto e : E[x]){
    if(bio[e] || e == p) continue;
    dfs_right(e, v, add, sum, mn, x);
  }
}

void solve(int x){
  dfs_sz(x);

  int centroid = 0;
  vector <int> lt, rt, lt_sum, rt_sum;
  lt.resize(sz[x] + 1); rt.resize(sz[x] + 1);

  find_centroid(x, sz[x], centroid, -1);
  dfs_left(centroid, lt, 1); dfs_right(centroid, rt, 1);

  bio[centroid] = true;

  for(auto e : E[centroid]){
    if(bio[e]) continue;

    int val = s[centroid] == '(' ? -1 : 1;
    dfs_left(e, lt, -1, val);
    dfs_right(e, rt, -1, val);

    vector <int> tmp_lt, tmp_rt;
    tmp_lt.resize(sz[e] + 1); tmp_rt.resize(sz[e] + 1);

    dfs_left(e, tmp_lt, 1);
    dfs_right(e, tmp_rt, 1);

    REP(i, sz(tmp_lt)){
      sol += (ll)tmp_lt[i] * rt[i];
      sol += (ll)tmp_rt[i] * lt[i];
    }
  }

  for(auto e : E[centroid]){
    if(bio[e]) continue;
    solve(e);
  }
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n;
  cin >> s;
  REP(i, n - 1){
    int a, b; cin >> a >> b; a --; b --;
    E[a].pb(b); E[b].pb(a);
  }

  solve(0);

  cout << sol;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 10 ms 7532 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 10 ms 7484 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 11 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 46864 KB Output is correct
2 Correct 879 ms 50920 KB Output is correct
3 Correct 867 ms 50980 KB Output is correct
4 Correct 840 ms 50984 KB Output is correct
5 Correct 863 ms 51076 KB Output is correct
6 Correct 853 ms 51064 KB Output is correct
7 Correct 866 ms 50936 KB Output is correct
8 Correct 852 ms 50928 KB Output is correct
9 Correct 859 ms 50988 KB Output is correct
10 Correct 730 ms 51084 KB Output is correct
11 Correct 726 ms 51216 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 10 ms 7532 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 10 ms 7484 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 11 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 868 ms 46864 KB Output is correct
12 Correct 879 ms 50920 KB Output is correct
13 Correct 867 ms 50980 KB Output is correct
14 Correct 840 ms 50984 KB Output is correct
15 Correct 863 ms 51076 KB Output is correct
16 Correct 853 ms 51064 KB Output is correct
17 Correct 866 ms 50936 KB Output is correct
18 Correct 852 ms 50928 KB Output is correct
19 Correct 859 ms 50988 KB Output is correct
20 Correct 730 ms 51084 KB Output is correct
21 Correct 726 ms 51216 KB Output is correct
22 Correct 1456 ms 27224 KB Output is correct
23 Correct 1446 ms 27752 KB Output is correct
24 Correct 1503 ms 27316 KB Output is correct
25 Correct 1599 ms 27248 KB Output is correct
26 Correct 1033 ms 35504 KB Output is correct
27 Correct 1041 ms 31788 KB Output is correct
28 Correct 1055 ms 30468 KB Output is correct
29 Correct 725 ms 50904 KB Output is correct
30 Correct 710 ms 50948 KB Output is correct
31 Correct 198 ms 27012 KB Output is correct
32 Correct 713 ms 50948 KB Output is correct