oj.uz

Submission #232886

# Submission time Handle Problem Language Result Execution time Memory
232886 2020-05-18T14:49:31 Z Saboon Zagrade (COI17_zagrade) C++14
10 / 100
 3000 ms 33860 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8576 KB Output is correct
2 Correct 78 ms 8696 KB Output is correct
3 Correct 77 ms 8576 KB Output is correct
4 Correct 82 ms 8696 KB Output is correct
5 Correct 83 ms 8704 KB Output is correct
6 Correct 76 ms 8696 KB Output is correct
7 Correct 77 ms 8704 KB Output is correct
8 Correct 78 ms 8676 KB Output is correct
9 Correct 80 ms 8576 KB Output is correct
10 Correct 75 ms 8576 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3076 ms 33860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8576 KB Output is correct
2 Correct 78 ms 8696 KB Output is correct
3 Correct 77 ms 8576 KB Output is correct
4 Correct 82 ms 8696 KB Output is correct
5 Correct 83 ms 8704 KB Output is correct
6 Correct 76 ms 8696 KB Output is correct
7 Correct 77 ms 8704 KB Output is correct
8 Correct 78 ms 8676 KB Output is correct
9 Correct 80 ms 8576 KB Output is correct
10 Correct 75 ms 8576 KB Output is correct
11 Execution timed out 3076 ms 33860 KB Time limit exceeded
12 Halted 0 ms 0 KB -