Submission #990635

#	Time	Username	Problem	Language	Result	Execution time	Memory
990635		ZeroCool	Zagrade (COI17_zagrade)	C++14	100 / 100	717 ms	60992 KiB

zagrade

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

using namespace __gnu_pbds;
using namespace std;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define ll long long
#define ar array
#define ld long double

//#define endl '\n'

const ll N = 4e5 + 20;
const ll INF = 1e17;
const int MOD = 1e9 + 7;

int n, A[N], del[N], ans, sz[N];
vector<int> g[N];
map<int,int> cnt;

int dfs1(int x,int p){
	sz[x] = 1;
	for(auto u : g[x]){
		if(u == p || del[u])continue;
		sz[x] += dfs1(u, x);
	}
	return sz[x];
}

int C(int x,int p,int s){
	for(auto u: g[x]){
		if(u == p || del[u])continue;
		if(sz[u] * 2 > s)return C(u, x, s);
	}
	return x;
}

void dfs2(int x,int p, int sum, int mn,int mx){
	sum += A[x];
	mx = max(mx, sum);
	mn = min(mn, sum);
	if(sum <= mn){
		ans += cnt[-mn];
	}
	for(auto u: g[x]){
		if(u == p || del[u])continue;
		dfs2(u, x, sum, mn, mx);
	}
}

void dfs3(int x,int p,int sum, int mn,int mx){
	sum += A[x];
	mx = max(mx, sum);
	mn = min(mn, sum);
	if(sum >= mx){
		cnt[sum]++;
	}
	for(auto u: g[x]){
		if(u == p || del[u])continue;
		dfs3(u, x, sum, mn, mx);
	}
}

void cen(int x){
	int c = C(x, x, dfs1(x, x));
	del[c] = 1;
	cnt.clear();
	if(A[c] == 1)cnt[A[c]]++;
	for(auto u: g[c]){
		if(del[u])continue;
		dfs2(u, c, 0, 0, 0);
		dfs3(u, c, A[c], min(A[c], 0ll), max(A[c], 0ll));
	}
	ans += cnt[0];
	cnt.clear();
	reverse(g[c].begin(), g[c].end());
	for(auto u: g[c]){
		if(del[u])continue;
		dfs2(u, c, 0, 0, 0);
		dfs3(u, c, A[c], min(A[c], 0ll), max(A[c], 0ll));
	}
	for(auto u: g[c]){
		if(!del[u])cen(u);
	}
}

void VladiDadi(){
	cin>>n;
	string s;
	cin>>s;
	for(int i = 0;i<n;i++)A[i] = (s[i] == '(' ? 1 : -1);
	for(int i =1 ;i<n;i++){
		int u, v;
		cin>>u>>v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cen(0);
	cout<<ans;
}



signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;

	
	//cin>>t;
	while(t--)
	VladiDadi();
}

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