oj.uz

Submission #232883

# Submission time Handle Problem Language Result Execution time Memory
232883 2020-05-18T14:43:26 Z Saboon Zagrade (COI17_zagrade) C++14
0 / 100
 45 ms 12132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;

const int maxn = 1e5 + 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;
	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;
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 7 ms 2688 KB Output is correct
3 Incorrect 7 ms 2816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 12132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 7 ms 2688 KB Output is correct
3 Incorrect 7 ms 2816 KB Output isn't correct
4 Halted 0 ms 0 KB -