Submission #1019576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019576		vjudge1	Zagrade (COI17_zagrade)	C++14	100 / 100	654 ms	48828 KiB

zagrade

#include <bits/stdc++.h>

#define N 300000

using namespace std;

int a[300005];

vector<int> g[300005];

int sz[300005];

int del[300005];

void pre_dfs(int u, int p) {
	sz[u] = 1;
	
	for (int v: g[u]) {
		if (v != p && del[v] == 0) {
			pre_dfs(v, u);
			sz[u] += sz[v];
		}
	}
}

int cent(int u, int p, int n) {
	for (int v: g[u]) {
		if (v != p && sz[v] > n / 2 && del[v] == 0) {
			return cent(v, u, n);
		}
	}
	
	return u;
}

int cnt[600005];

long long ans = 0;

void dfs(int u, int p, int s, int k, int type) {
	if (type == 0) {
		if (s == min(k, s)) {
			ans += cnt[-s + N];
		}
	} else if (type == 1) {		
		if (min(a[u], a[u] + k) >= 0) {
			cnt[s + N]++;
		}
	} else {
		if (min(a[u], a[u] + k) >= 0) {
			cnt[s + N]--;
		}
	}
	
	for (int v: g[u]) {
		if (v != p && del[v] == 0) {
			if (type == 0) {
				dfs(v, u, s + a[v], min(k, s), type);
			} else {
				dfs(v, u, s + a[v], min(a[u], a[u] + k), type);
			}
		}
	}
}

void upd(int r) {
	
	if (a[r] == 1) {
		cnt[N + 1] = 1; 
	}
	
	for (int v: g[r]) {
		if (del[v] == 0) {
			dfs(v, r, a[v], 0, 0);
			dfs(v, r, a[r] + a[v], a[r], 1);
		}
	}
	
	for (int v: g[r]) {
		if (del[v] == 0) {
			dfs(v, r, a[r] + a[v], a[r], 2);
		}
	}
	
	if (a[r] == 1) {
		cnt[N + 1] = 0;
	}
}

void solve(int u) {
	pre_dfs(u, u);
	
	int r = cent(u, u, sz[u]);
	
	upd(r);
	
	del[r] = 1;
	
	for (int v: g[r]) {
		if (del[v] == 0) {
			solve(v);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;

	cin >> n;
	
	string s;

	cin >> s;
	
	s = '&' + s;
	
	for (int i = 1; i <= n; ++i) {
		a[i] = (s[i] == '(' ? 1 : -1);
	}
	
	for (int i = 1; i <= n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	
	memset(del, 0, sizeof del);
	
	solve(1);
	
	for (int i = 1; i <= n; ++i) {
		a[i] *= -1;
	}
	
	memset(del, 0, sizeof del);
	
	solve(1);
	
	cout << ans << '\n';
	
}

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