Submission #232314

#	Time	Username	Problem	Language	Result	Execution time	Memory
232314		pedy4000	Zagrade (COI17_zagrade)	C++14	10 / 100	3055 ms	78732 KiB

zagrade

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int N = 3e5 + 15, LOG = 20;
int n, ans;
string s;
int deep[N], up[N], ok[N], OK[N];
bool neg[N];
int ind[N], T;
int par[LOG][N];
vector <int> G[N], GP[N];
vector <int> ver[N];

void calc (int v = 0, int p = 0) {
	par[0][v] = p;
	for (int i = 1; i < LOG; i++)
		par[i][v] = par[i - 1][par[i - 1][v]];

	ind[T++] = v;

	deep[v] = 1 + deep[p];
	up[v] = up[p] + (s[v] == '('? +1: -1);

	ok[v] = v;
	if (s[v] == '(') {
		int u = ok[p];
		if (u != p && u != par[0][u])
			u = par[0][u];
		if (u != par[0][u] && s[par[0][u]] == '(')
			u = ok[par[0][u]];

		ok[v] = u;
	}
	OK[v] = v;
	if (s[v] == ')') {
		int u = OK[p];
		if (u != p && u != par[0][u])
			u = par[0][u];
		if (u != par[0][u] && s[par[0][u]] == ')')
			u = OK[par[0][u]];

		OK[v] = u;
	}

	for (int u: G[v])
		if (u != p)
			calc(u, v);
}

int lca (int v, int u) {
	if (deep[v] < deep[u])
		swap(v, u);
	int dis = deep[v] - deep[u];
	for (int i = 0; i < LOG; i++)
		if ((dis >> i) & 1)
			v = par[i][v];
	if (v == u)
		return v;
	for (int i = LOG - 1; ~i; i--)
		if (par[i][v] != par[i][u]) {
			v = par[i][v];
			u = par[i][u];
		}
	return par[0][v];
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> s;
	for (int i = 0; i < n - 1; i++) {
		int v, u;
		cin >> v >> u;
		v--, u--;

		G[v].push_back(u);
		G[u].push_back(v);
	}

	calc();

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;

			int k = lca(i, j);

			if (k == i) {
				if (deep[OK[j]] <= deep[i] && up[j] - up[i] == -((s[i] == '('? +1: -1))) {
					ans++;
				}
				continue;
			}
			if (k == j) {
				if (deep[ok[i]] <= deep[j] && up[i] - up[j] == -((s[j] == '('? +1: -1)))
					ans++;
				continue;
			}
			if (deep[ok[i]] <= deep[k] && deep[OK[j]] <= deep[k] && up[i] - up[k] + up[j] - up[k] == -((s[k] == '('? +1: -1)))
				ans++;
		}
	cout << ans << "\n";
	return 0;
}

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