Submission #419560

#	Time	Username	Problem	Language	Result	Execution time	Memory
419560		mosiashvililuka	Zagrade (COI17_zagrade)	C++17	100 / 100	1335 ms	47576 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,bo[300009],cnt,p[300009],pi,msh[300009],dp[300009];
long long pas;
vector <int> v[300009];
int A[300009],Ai,Bi;
pair <int, int> B[300009];
//vector <int> vv[300009];
int fx[300009],k[300009];
string s;
char ch;
void dfs(int q, int w){
	pi++;p[pi]=q;
	msh[q]=w;
	dp[q]=1;
	for(vector <int>::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(int q, int w, int rr, int mn){
	int RR,MN;
	if(s[q]=='('){
		RR=rr+1;MN=min(1,mn+1);
	}else{
		RR=rr-1;MN=min(-1,mn-1);
	}
	if(MN>=0){
		Ai++;A[Ai]=RR;
	}
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||bo[(*it)]==1) continue;
		dfs2((*it),q,RR,MN);
	}
}
void dfs3(int q, int w, int rr, int mn, int mn2){
	int RR,MN,MN2;
	if(s[q]==')'){
		RR=rr+1;MN=min(1,mn+1);
		MN2=max(mn2,RR);
	}else{
		RR=rr-1;MN=min(-1,mn-1);
		MN2=max(mn2,RR);
	}
	if(MN>=0){
		Bi++;
		//B[Bi].first=RR;B[Bi].second=MN2;
		B[Bi].first=MN2;B[Bi].second=RR;
	}
	for(vector <int>::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;
	sort(B+1,B+Bi+1);
	sort(A+1,A+Ai+1);
	j=1;
	for(i=1; i<=Ai; i++){
		while(j<=Bi&&B[j].first<=A[i]){
			if(fx[B[j].second]!=cnt){
				fx[B[j].second]=cnt;
				k[B[j].second]=1;
			}else{
				k[B[j].second]++;
			}
			j++;
		}
		if(fx[A[i]]==cnt) sm+=k[A[i]];
	}
	/*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(int q, int w, int rr){
	if(s[q]=='('){
		rr++;
	}else{
		rr--;
	}
	if(rr<0) return;
	if(rr==0) pas++;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||bo[(*it)]==1) continue;
		dfsa((*it),q,rr);
	}
}
void dfsb(int q, int w, int rr){
	if(s[q]==')'){
		rr++;
	}else{
		rr--;
	}
	if(rr<0) return;
	if(rr==0) pas++;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w||bo[(*it)]==1) continue;
		dfsb((*it),q,rr);
	}
}
void rec(int q){
	pi=0;
	dfs(q,0);
	int zz=0;
	for(int h=1; h<=pi; h++){
		bool boo=0;
		for(vector <int>::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 <int>::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 <int>::iterator it=v[zz].begin(); it!=v[zz].end(); it++){
		if(bo[(*it)]==1) continue;
		int 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 <int>::iterator it=v[zz].begin(); it!=v[zz].end(); it++){
		if(bo[(*it)]==1) continue;
		Ai=0;Bi=0;
		int 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 <int>::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;
	scanf("%d\n",&a);
	/*cin>>s;
	s.insert(0,"0");*/
	s+="0";
	for(i=1; i<=a; i++){
		ch=getchar();
		s.push_back(ch);
	}
	for(i=1; i<a; i++){
		//cin>>c>>d;
		if(i!=a-1) scanf("%d %d\n",&c,&d); else scanf("%d %d",&c,&d);
		v[c].push_back(d);
		v[d].push_back(c);
	}
	rec(1);
	//cout<<pas;
	printf("%llu",pas);
	return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:191:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |  scanf("%d\n",&a);
      |  ~~~~~^~~~~~~~~~~
zagrade.cpp:201:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |   if(i!=a-1) scanf("%d %d\n",&c,&d); else scanf("%d %d",&c,&d);
      |              ~~~~~^~~~~~~~~~~~~~~~~
zagrade.cpp:201:48: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |   if(i!=a-1) scanf("%d %d\n",&c,&d); else scanf("%d %d",&c,&d);
      |                                           ~~~~~^~~~~~~~~~~~~~~

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