Submission #209728

#	Time	Username	Problem	Language	Result	Execution time	Memory
209728		ruler	Zagrade (COI17_zagrade)	C++14	10 / 100	3071 ms	46164 KiB

zagrade

// IOI 2021
#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 3e5 + 2;

int n, A[N], SZ[N];
bool M[N];
vector<int> G[N];
ll ans;

void DFSZ(int v, int p = 0) {
	SZ[v] = 1;
	for (int u : G[v])
		if (u != p && !M[u])
			DFSZ(u, v), SZ[v] += SZ[u];
}
int GetCentroid(int v, int p = 0, int m = 0) {
	if (!p) DFSZ(v), m = SZ[v];
	for (int u : G[v])
		if (u != p && !M[u] && SZ[u] * 2 > m)
			return GetCentroid(u, v, m);
	return v;
}
void DFS(int v, vector<int> &c, bool r, int x, int p = 0, int s = 0, int m = 0) {
	s += A[v], m += A[v];
	if (r) s *= -1, m *= -1;
	m = min(m, 0);
	if (m >= 0 && s >= 0) c[s] += x;
	if (r) s *= -1, m *= -1;
	for (int u : G[v])
		if (u != p && !M[u])
			DFS(u, c, r, x, v, s, m);
}
void Solve(int v) {
	vector<int> up(n + 1, 0), dw(n + 1, 0);
	DFS(v, up, 1, + 1), DFS(v, dw, 0, + 1);	
	for (int u : G[v]) if (!M[u]) {
		DFS(u, up, 1, - 1, v, A[v]), DFS(u, dw, 0, - 1, v, A[v]);	
		vector<int> cup(n + 1, 0), cdw(n + 1, 0);
		DFS(u, cup, 1, + 1, v), DFS(u, cdw, 0, + 1, v);
		for (int i = 0; i < n + 1; i++) ans += 1LL * cup[i] * dw[i] + 1LL * cdw[i] * up[i];
	}
}
void Decompose(int v) {
	v = GetCentroid(v), M[v] = 1, Solve(v);
	for (int u : G[v]) if (!M[u]) Decompose(u);
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	cin >> n;
	for (int i = 0; i < n; i++) {
		char c; cin >> c;
		if (c == '(') A[i + 1] = + 1;
		else A[i + 1] = - 1;
	}
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		G[v].push_back(u);
		G[u].push_back(v);
	}
	Decompose(1);
	cout << ans << endl;

	return 0;
}

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