Submission #232318

#	Time	Username	Problem	Language	Result	Execution time	Memory
232318		pedy4000	Zagrade (COI17_zagrade)	C++14	40 / 100	179 ms	38028 KiB

zagrade

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

typedef long long ll;

const int N = 3e5 + 15, LOG = 20;
ll 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];
int dp[N], ls[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);
	}

	if (n <= 4000) {
		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;
	}
	for (int T = 0; T < 2; T++) {
		for (int i = n - 1; ~i; i--) {
			ls[i] = -1;
			dp[i] = 0;
			if (s[i] == ')')
				continue;
			if (i == n - 1)
				continue;

			int ind = i + 1;
			while (ind < n && s[ind] == '(' && ls[ind] != -1)
				ind = ls[ind] + 1;
			
			if (ind == n)
				continue;
			if (s[ind] == '(')
				continue;

			ls[i] = ind;
			dp[i] = 1 + dp[ind + 1];
		}

		for (int i = 0; i < n; i++)
			ans += dp[i];
		reverse(s.begin(), s.end());
	}
	cout << ans << "\n";
	return 0;
}

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