Submission #545211

#	Time	Username	Problem	Language	Result	Execution time	Memory
545211		hollwo_pelw	Zagrade (COI17_zagrade)	C++17	100 / 100	1300 ms	49364 KiB

zagrade

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen("A.inp", "r"))
		assert(freopen("A.inp", "r", stdin)), assert(freopen("A.out", "w", stdout));
#else
	auto start = chrono::steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 3e5 + 5;

int n, a[N];
vector<int> adj[N];
char s[N];

int siz[N], mark[N];

#define for_cen(v, u) for (int v : adj[u]) if (!mark[v])

long long res;

int find_sz(int u, int p) {
	siz[u] = 1;
	for_cen(v, u) if (v != p)
		siz[u] += find_sz(v, u);
	return siz[u];
}

int find_cen(int u, int p, const int &tot) {
	for_cen(v, u) if (v != p)
		if (siz[v] > tot / 2)
			return find_cen(v, u, tot);
	return u;
}

struct freq_array {
	int cnt[N], ver[N], vercnt;

	inline void clear() { vercnt ++; }
	inline void add(int p, int v) {
		// cout << "add " << p << ' ' << v << '\n';
		if (p < 0) return ;
		if (ver[p] ^ vercnt)
			ver[p] = vercnt, cnt[p] = 0;
		cnt[p] += v;
	}
	inline int query(int p) {
		if (p < 0) return 0;
		if (ver[p] ^ vercnt)
			ver[p] = vercnt, cnt[p] = 0;
		// cout << "query " << p << ' ' << cnt[p] << '\n';
		return cnt[p];
	}
} cnt;

int val_up[N], min_up[N];
int val_dw[N], min_dw[N];

void pre_dfs(int u, int p) {
	for_cen(v, u) if (v != p) {
		val_dw[v] = val_dw[u] + a[v];
		min_dw[v] = min(min_dw[u], val_dw[v]);

		val_up[v] = val_up[u] + a[v];
		min_up[v] = min(0 , min_up[u] + a[v]);

		pre_dfs(v, u);
	}
}

void dfs_query(int u, int p) {
	if (val_dw[u] == min_dw[u]) {
		// cout << "u = " << u << " -> ";
		res += cnt.query(-val_dw[u]);
	}
	for_cen(v, u) if (v != p)
		dfs_query(v, u);
}

void dfs_update(int u, int p, int w) {
	if (min_up[u] >= 0) {
		// cout << "u = " << u << " -> ";
		cnt.add(val_up[u], w);
	}
	for_cen(v, u) if (v != p)
		dfs_update(v, u, w);
}

void centroid_decomp(int r) {
	int tot = find_sz(r, r);
	r = find_cen(r, r, tot);

	// cout << "SOLVE " << r << ' ' << tot << '\n';

	val_up[r] = a[r];
	min_up[r] = min(a[r], 0);
	val_dw[r] = min_dw[r] = 0;
	pre_dfs(r, r);

	cnt.clear();
	dfs_update(r, r, 1);
	dfs_query(r, r);

	for_cen(v, r) {
		cnt.clear();
		dfs_update(v, r, -1);
		dfs_query(v, r);
	}

	mark[r] = 1;
	for_cen(v, r)
		centroid_decomp(v);

}

void Hollwo_Pelw(){
	cin >> n >> (s + 1);
	for (int i = 1; i <= n; i++)
		a[i] = s[i] == '(' ? 1 : -1;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	centroid_decomp(1);

	cout << res << '\n';
}

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