Submission #232886

#	Time	Username	Problem	Language	Result	Execution time	Memory
232886		Saboon	Zagrade (COI17_zagrade)	C++14	10 / 100	3076 ms	33860 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;

const int maxn = 3e5 + 10;

string s;
vector<int> t[maxn];
int sz[maxn];
bool mark[maxn];
ll answer = 0, ans2;
int cnt[maxn];

void dfs2(int v, int mnm, int sum, int par = -1){
	if (s[v] == '(')
		sum ++;
	else
		sum --;
	mnm = min(mnm, sum);
	if (mnm == sum){
		cnt[-mnm] ++;
		if (mnm == 0)
			ans2 ++;
	}
	for (auto u : t[v])
		if (!mark[u] and u != par)
			dfs2(u, mnm, sum, v);
}

void dfs1(int v, int need, int sum, int par = -1){
	if (s[v] == '('){
		need = max(need - 1, 0);
		sum ++;
	}
	else{
		need ++;
		sum --;
	}
	if (need == 0)
		answer += cnt[sum];
	for (auto u : t[v])
		if (!mark[u] and u != par)
			dfs1(u, need, sum, v);
}

int dfssz(int v, int par = -1){
	sz[v] = 1;
	for (auto u : t[v])
		if (!mark[u] and u != par)
			sz[v] += dfssz(u, v);
	return sz[v];
}

void centroidDecomposition(int v){
	int Max = dfssz(v), par = -1;
	bool found = 1;
	while (found){
		found = 0;
		for (auto u : t[v])
			if (!mark[u] and u != par and 2*sz[u] >= Max){
				par = v, v = u, found = 1;
				break;
			}
	}
	if (s[v] == ')')
		cnt[1] ++;
	for (auto u : t[v]){
		if (mark[u])
			continue;
		dfs1(u, 0, 0, v);
		int mnm = 0, sum = 0;
		if (s[v] == '(')
			sum ++;
		else
			mnm = sum = -1;
		dfs2(u, mnm, sum, v);
	}
	cnt[0] = 0;
	memset(cnt, 0, sizeof cnt);
	for (int i = 1; cnt[i] > 0; i++)
		cnt[i] = 0;
	reverse(t[v].begin(), t[v].end());
	for (auto u : t[v]){
		if (mark[u])
			continue;
		dfs1(u, 0, 0, v);
		int mnm = 0, sum = 0;
		if (s[v] == '(')
			sum ++;
		else
			mnm = sum = -1;
		dfs2(u, mnm, sum, v);
	}
	cnt[0] = 0;
	memset(cnt, 0, sizeof cnt);
	for (int i = 1; cnt[i] > 0; i++)
		cnt[i] = 0;
	mark[v] = 1;
	for (auto u : t[v])
		if (!mark[u])
			centroidDecomposition(u);
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	cin >> s;
	s = "#" + s;
	for (int i = 1; i <= n-1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	centroidDecomposition(1);
	cout << answer + ans2/2 << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60