Submission #1308828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308828		vili	Zagrade (COI17_zagrade)	C++20	0 / 100	3096 ms	48668 KiB

zagrade

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

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

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

vector<int>v[N];

int sz[N];
int flg[N];
int rj;
string s;
map<pair<int,pii>,int>map2;
vector<pair<int,pii>>rlb;

void dfs(int tr,int pr=-1) {
	
	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;
}
pii br3;
void dfs2(int tr,pii br,pii br2,int pr = -1) {
	if (s[tr]=='(') br.X++;
	else {
		if (br.X>0) br.X--;
		else br.Y++;
	}
	// drugi
	if (s[tr]==')') br2.Y++;
	else {
		if (br2.Y>0) br2.Y--;
		else br2.X++; 
	}
	if (s[tr]==')') br3.Y++;
	else {
		if (br3.Y>0) br3.Y--;
		else br3.X++; 
	}
	
	if (br.X==0) rj+=map2[{2,{br.Y,br.X}}];
	if (br2.Y==0) rj+=map2[{1,{br2.Y,br2.X}}];
	if (br3.X==0 and br3.Y==0) rj++;
	
	//cout <<tr<<" :: "<<br.X<<" "<<br.Y<< " :: "<<br2.X<<" "<<br2.Y<<" >. "<<br3.X<<" "<<br3.Y<<endl;
	//cout << map2[{2,{br.Y,br.X}}]<<" + "<<map2[{1,{br2.Y,br2.X}}]<<endl;
	
	rlb.PB({1,br});
	rlb.PB({2,br2});
	
	
	for (int i=0;i<v[tr].size();i++) {
		if (v[tr][i]==pr or flg[v[tr][i]]==1) continue;
		dfs2(v[tr][i],br,br2,tr);
	}
	
}


void cnt(int tr) {
	dfs(tr);
	if (sz[tr]==1) return;
	int tr2=fnd_cnt(tr,sz[tr]);
	flg[tr2]=1;
	// izracunaj start
	//cout <<tr2<<"START"<<endl;
	map2.clear();
	
	pii aa = {0,0};
	if (s[tr2]=='(') aa.X++;
	else aa.Y++;
	
	map2[{2,{0,0}}]=1;

	for (int i=0;i<v[tr2].size();i++) {
		if (flg[v[tr2][i]]==1) continue;
		br3=aa;
		dfs2(v[tr2][i],aa,{0,0});
		
		//cout<<"NOVO"<<endl;
				
		while (!rlb.empty()) {
			map2[rlb.back()]++;
			rlb.pop_back();
		}
	}
	//rj+=map2[{2,{aa.Y,aa.X}}];
	//cout << map2[{2,{aa.Y,aa.X}}]<< " DODANO "<<endl;
	
	// izracunaj end
	
	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;
}

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

}

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