oj.uz

Submission #232318

# Submission time Handle Problem Language Result Execution time Memory
232318 2020-05-16T16:42:06 Z pedy4000 Zagrade (COI17_zagrade) C++14
40 / 100
 179 ms 38028 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 21760 KB Output is correct
2 Correct 104 ms 21760 KB Output is correct
3 Correct 101 ms 21632 KB Output is correct
4 Correct 102 ms 21816 KB Output is correct
5 Correct 98 ms 21812 KB Output is correct
6 Correct 99 ms 21760 KB Output is correct
7 Correct 103 ms 21632 KB Output is correct
8 Correct 104 ms 21880 KB Output is correct
9 Correct 101 ms 21760 KB Output is correct
10 Correct 84 ms 21760 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 33676 KB Output is correct
2 Correct 124 ms 33548 KB Output is correct
3 Correct 124 ms 33544 KB Output is correct
4 Correct 128 ms 33504 KB Output is correct
5 Correct 123 ms 33548 KB Output is correct
6 Correct 124 ms 33548 KB Output is correct
7 Correct 124 ms 33420 KB Output is correct
8 Correct 121 ms 33676 KB Output is correct
9 Correct 127 ms 33672 KB Output is correct
10 Correct 129 ms 33548 KB Output is correct
11 Correct 125 ms 33548 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 21760 KB Output is correct
2 Correct 104 ms 21760 KB Output is correct
3 Correct 101 ms 21632 KB Output is correct
4 Correct 102 ms 21816 KB Output is correct
5 Correct 98 ms 21812 KB Output is correct
6 Correct 99 ms 21760 KB Output is correct
7 Correct 103 ms 21632 KB Output is correct
8 Correct 104 ms 21880 KB Output is correct
9 Correct 101 ms 21760 KB Output is correct
10 Correct 84 ms 21760 KB Output is correct
11 Correct 127 ms 33676 KB Output is correct
12 Correct 124 ms 33548 KB Output is correct
13 Correct 124 ms 33544 KB Output is correct
14 Correct 128 ms 33504 KB Output is correct
15 Correct 123 ms 33548 KB Output is correct
16 Correct 124 ms 33548 KB Output is correct
17 Correct 124 ms 33420 KB Output is correct
18 Correct 121 ms 33676 KB Output is correct
19 Correct 127 ms 33672 KB Output is correct
20 Correct 129 ms 33548 KB Output is correct
21 Correct 125 ms 33548 KB Output is correct
22 Incorrect 179 ms 38028 KB Output isn't correct
23 Halted 0 ms 0 KB -