Submission #419533

#	Time	Username	Problem	Language	Result	Execution time	Memory
419533		mosiashvililuka	Zagrade (COI17_zagrade)	C++17	40 / 100	3058 ms	61660 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,bo[300009],cnt,p[300009],pi,msh[300009],dp[300009],pas;
vector <long long> v[300009];
long long A[300009],Ai,Bi;
pair <long long, long long> B[300009];
vector <long long> vv[300009];
long long fx[300009];
string s;
void dfs(long long q, long long w){
	pi++;p[pi]=q;
	msh[q]=w;
	dp[q]=1;
	for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||bo[(*it)]==1) continue;
		dfs((*it),q);
		dp[q]+=dp[(*it)];
	}
}
void dfs2(long long q, long long w, long long rr, long long mn){
	long long RR,MN;
	if(s[q]=='('){
		RR=rr+1;MN=min(1LL,mn+1);
	}else{
		RR=rr-1;MN=min(-1LL,mn-1);
	}
	if(MN>=0){
		Ai++;A[Ai]=RR;
	}
	for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||bo[(*it)]==1) continue;
		dfs2((*it),q,RR,MN);
	}
}
void dfs3(long long q, long long w, long long rr, long long mn, long long mn2){
	long long RR,MN,MN2;
	if(s[q]==')'){
		RR=rr+1;MN=min(1LL,mn+1);
		MN2=max(mn2,RR);
	}else{
		RR=rr-1;MN=min(-1LL,mn-1);
		MN2=max(mn2,RR);
	}
	if(MN>=0){
		Bi++;
		B[Bi].first=RR;B[Bi].second=MN2;
	}
	for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||bo[(*it)]==1) continue;
		dfs3((*it),q,RR,MN,MN2);
	}
}
long long fun(){
	long long sm=0;
	for(i=1; i<=Bi; i++){
		if(fx[B[i].first]!=cnt){
			fx[B[i].first]=cnt;vv[B[i].first].clear();
		}
		vv[B[i].first].push_back(B[i].second);
	}
	for(i=1; i<=Bi; i++){
		if(i!=1&&B[i-1].first==B[i].first) continue;
		sort(vv[B[i].first].begin(),vv[B[i].first].end());
	}
	for(i=1; i<=Ai; i++){
		if(fx[A[i]]!=cnt) continue;
		c=lower_bound(vv[A[i]].begin(),vv[A[i]].end(),A[i]+1)-vv[A[i]].begin();
		sm+=c;
	}
	return sm;
}
void dfsa(long long q, long long w, long long rr){
	if(s[q]=='('){
		rr++;
	}else{
		rr--;
	}
	if(rr<0) return;
	if(rr==0) pas++;
	for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||bo[(*it)]==1) continue;
		dfsa((*it),q,rr);
	}
}
void dfsb(long long q, long long w, long long rr){
	if(s[q]==')'){
		rr++;
	}else{
		rr--;
	}
	if(rr<0) return;
	if(rr==0) pas++;
	for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||bo[(*it)]==1) continue;
		dfsb((*it),q,rr);
	}
}
void rec(long long q){
	pi=0;
	dfs(q,0);
	long long zz=0;
	for(long long h=1; h<=pi; h++){
		bool boo=0;
		for(vector <long long>::iterator it=v[p[h]].begin(); it!=v[p[h]].end(); it++){
			if((*it)==msh[p[h]]||bo[(*it)]==1) continue;
			if(dp[(*it)]>pi/2){
				boo=1;
				break;
			}
		}
		if(pi-dp[p[h]]>pi/2) boo=1;
		if(boo==0){
			zz=p[h];
			break;
		}
	}
	//cout<<q<<" A "<<zz<<endl;
	Ai=0;Bi=0;
	/*if(s[zz]=='('){
		Ai++;
		A[Ai]=1;
	}*/
	for(vector <long long>::iterator it=v[zz].begin(); it!=v[zz].end(); it++){
		if(bo[(*it)]==1) continue;
		if(s[zz]=='('){
			dfsa((*it),zz,1);
		}else{
			dfsb((*it),zz,1);
		}
	}
	//cout<<pas<<endl;
	for(vector <long long>::iterator it=v[zz].begin(); it!=v[zz].end(); it++){
		if(bo[(*it)]==1) continue;
		long long as=0,sd=0;
		if(s[zz]=='('){
			as=1;sd=1;
		}else{
			as=-1;sd=-1;
		}
		dfs2((*it),zz,as,sd);
		dfs3((*it),zz,0,0,0);
	}
	cnt++;
	pas+=fun();
	for(vector <long long>::iterator it=v[zz].begin(); it!=v[zz].end(); it++){
		if(bo[(*it)]==1) continue;
		Ai=0;Bi=0;
		long long as=0,sd=0;
		if(s[zz]=='('){
			as=1;sd=1;
			/*Ai++;
			A[Ai]=1;*/
		}else{
			as=-1;sd=-1;
		}
		dfs2((*it),zz,as,sd);
		dfs3((*it),zz,0,0,0);
		cnt++;
		pas-=fun();
	}
	bo[zz]=1;
	//cout<<q<<" B "<<zz<<endl;
	//cout<<pas<<endl;
	for(vector <long long>::iterator it=v[zz].begin(); it!=v[zz].end(); it++){
		if(bo[(*it)]==1) continue;
		rec((*it));
	}
	//cout<<q<<" C "<<zz<<endl;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	cin>>s;
	s.insert(0,"0");
	for(i=1; i<a; i++){
		cin>>c>>d;
		v[c].push_back(d);
		v[d].push_back(c);
	}
	rec(1);
	cout<<pas;
	return 0;
}

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