Submission #545736

#	Time	Username	Problem	Language	Result	Execution time	Memory
545736		ace_in_the_hole	Zagrade (COI17_zagrade)	C++14	0 / 100	3090 ms	1048576 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;

typedef long long Int;
typedef long double Real;

const int MOD = 2004010501; //MOD > 2e9

const int N = 3e5 + 5;
int num_nodes; char ch[N];
vector<int> tree[N];

bool done[N];
int siz[N];
void calc_siz(int u, int pa) {
	siz[u] = 1;
	for (auto v : tree[u])
		if (!done[v] and v != pa) calc_siz(v,u), siz[u] += siz[v];
}
int centroid(int u, int pa, int total) {
	for (auto v : tree[u])
		if (!done[v] and v != pa and 2*siz[v] > total)
			return centroid(v,u,total);
	return u;
}

/*
tiền tố A, hậu tố B
. O(a,i) - C(a,i) >= 0
. C(b,i) - O(b,i) >= 0
. O(a)-C(a) + O(b)-C(b) = 0
delta(a) = -delta(b)
-N <= delta <= N
khi dfs xuống, duy trì min
*/
const int MIN = -N;
const int MAX = +N;
int freq_pref[MAX-MIN+1];
int freq_suff[MAX-MIN+1];
#define fre_p(x) freq_pref[x-MIN]
#define fre_s(x) freq_suff[x-MIN]

struct Info {
	int s1,m1,s2,m2;
	Info() { s1 = s2 = m1 = m2 = 0; }
	void add(char p) {
		int d = (p == '(') ? +1 : -1;
		m1 = min(s1+=d, m1+d);
		m2 = min(s2-=d, m2-d);
	}
};

void dfs_update(int u, int pa, Info val, int add) {
	val.add(ch[u]);
	if (val.m1 >= 0) fre_p(val.s1) += add;
	if (val.m2 >= 0) fre_s(val.s2) += add;
	for (auto v : tree[u]) if (!done[v] and v != pa)
		dfs_update(v,u,val,add);
}

Int answer = 0;
void dfs_query(int u, int pa, Info val) {
	val.add(ch[u]);
	if (val.m1 >= 0) answer += fre_s(val.s1);
	if (val.m2 >= 0) answer += fre_p(val.s2);
	for (auto v : tree[u]) if (!done[v] and v != pa)
		dfs_query(v,u,val);
}

void centroid_decompose(int u) {
	calc_siz(u,-1);
	int g = centroid(u, -1, siz[u]);
	done[g] = true;
	Info root; root.add(ch[g]);
	if (root.m1 >= 0) ++fre_p(root.s1);
	if (root.m2 >= 0) ++fre_s(root.s2);
	for (auto v : tree[g]) {
		dfs_query(v,g, Info());
		dfs_update(v,g, root, +1);
	}
	if (root.m1 >= 0) --fre_p(root.s1);
	if (root.m2 >= 0) --fre_s(root.s2);
	for (auto v : tree[g])
		dfs_update(v,g, root, -1);
	for (auto v : tree[g])
		centroid_decompose(v);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> num_nodes;
	for (int i = 1; i <= num_nodes; i++) cin >> ch[i];
	for (int u,v, i = 1; i < num_nodes; i++) {
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}

	centroid_decompose(1);
	cout << answer;
}

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