Submission #144393

#	Time	Username	Problem	Language	Result	Execution time	Memory
144393		Milki	Zagrade (COI17_zagrade)	C++14	100 / 100	1599 ms	51216 KiB

zagrade

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60