Submission #1308849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308849		vili	Zagrade (COI17_zagrade)	C++20	0 / 100	424 ms	42828 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define int LL
#define X first
#define Y second
#define PB push_back
#define INS insert
#define pii pair<int,int>

const int N = 6e5;
const int INF = 1e9;
const int MOD = 1e9+7;

vector<int>v[N];

vector<int>rb;
int sz[N];
int flg[N];
int rj;
string s;
int put[N];

void dfs(int tr,int pr=-1) {
	sz[tr]=0;
	for (int i=0;i<v[tr].size();i++) {
		if (v[tr][i]==pr or flg[v[tr][i]]==1) continue;
		dfs(v[tr][i],tr);
		
		sz[tr]+=sz[v[tr][i]];
		
	}
	sz[tr]++;
}
int fnd_cnt(int tr,int n,int pr = -1) {
	for (int i=0;i<v[tr].size();i++) {
		if (v[tr][i]==pr or flg[v[tr][i]]==1) continue;
		if (sz[v[tr][i]]*2>n) return fnd_cnt(v[tr][i],n,tr);
	}
	return tr;
}
int zbroji(char a) {
	if (a=='(') return 1;
	else return -1;
}
void umi(int tr,int pr,bool cnt,int br,int brm,int md) {
	br+=zbroji(s[tr]);
	brm+=zbroji(s[tr]);
	brm=min(0ll,brm);
	md=min(md,br);
	
	if (cnt and br<=0 and br==md) {
		rj += put[-br];
	}
	else if (brm>=0 and br>=0) put[br]++;
	
	for (int i=0;i<v[tr].size();i++) {
		if (flg[v[tr][i]]==1 or pr==v[tr][i]) continue;
		umi(v[tr][i],tr,cnt,br,brm,md);
	}
}
void cnt(int tr) {
	dfs(tr);
	if (sz[tr]==1) return;
	int tr2=fnd_cnt(tr,sz[tr]);
	flg[tr2]=1;
	
	
	put[0]++;
	for (int i=0;i<v[tr2].size();i++) {
		if (flg[v[tr2][i]]==1) continue;
		umi(v[tr2][i],tr2,true,zbroji(s[tr2]),zbroji(s[tr2]),zbroji(s[tr2]));
		umi(v[tr2][i],tr2,false,0,0,0);
		
	}
	if (zbroji(s[tr2]) < 0) rj+=put[-zbroji(s[tr2])];
	for (int i=0;i<sz[tr]+1000;i++) put[i]=0;
	
	reverse(v[tr2].begin(),v[tr2].end());
	for (int i=0;i<v[tr2].size();i++) {
		if (flg[v[tr2][i]]==1) continue;
		umi(v[tr2][i],tr2,true,zbroji(s[tr2]),zbroji(s[tr2]),zbroji(s[tr2]));
		umi(v[tr2][i],tr2,false,0,0,0);
	}
	for (int i=0;i<sz[tr]+1000;i++) put[i]=0;
	

	
	for (int i=0;i<v[tr2].size();i++) {
		if (flg[v[tr2][i]]) continue;
		cnt(v[tr2][i]);	
	}
	
	
	
}
void solve() {
	int n,a,b; 
	cin>>n;
	cin>>s;
	s='0'+s;
	for (int i=0;i<n-1;i++) {
		int a,b;
		cin>>a>>b;
		v[a].PB(b);
		v[b].PB(a);
	}
	cnt(1);
	
	cout << rj;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();

}

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