oj.uz

Submission #419560

# Submission time Handle Problem Language Result Execution time Memory
419560 2021-06-07T09:30:22 Z mosiashvililuka Zagrade (COI17_zagrade) C++17
100 / 100
 1335 ms 47576 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7472 KB Output is correct
3 Correct 6 ms 7440 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 40512 KB Output is correct
2 Correct 774 ms 41828 KB Output is correct
3 Correct 586 ms 40596 KB Output is correct
4 Correct 719 ms 41620 KB Output is correct
5 Correct 588 ms 40548 KB Output is correct
6 Correct 652 ms 40800 KB Output is correct
7 Correct 579 ms 40604 KB Output is correct
8 Correct 635 ms 40804 KB Output is correct
9 Correct 621 ms 40524 KB Output is correct
10 Correct 755 ms 43360 KB Output is correct
11 Correct 621 ms 42452 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7472 KB Output is correct
3 Correct 6 ms 7440 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 612 ms 40512 KB Output is correct
12 Correct 774 ms 41828 KB Output is correct
13 Correct 586 ms 40596 KB Output is correct
14 Correct 719 ms 41620 KB Output is correct
15 Correct 588 ms 40548 KB Output is correct
16 Correct 652 ms 40800 KB Output is correct
17 Correct 579 ms 40604 KB Output is correct
18 Correct 635 ms 40804 KB Output is correct
19 Correct 621 ms 40524 KB Output is correct
20 Correct 755 ms 43360 KB Output is correct
21 Correct 621 ms 42452 KB Output is correct
22 Correct 1174 ms 22760 KB Output is correct
23 Correct 1222 ms 27004 KB Output is correct
24 Correct 1318 ms 26852 KB Output is correct
25 Correct 1335 ms 27120 KB Output is correct
26 Correct 755 ms 32268 KB Output is correct
27 Correct 750 ms 29412 KB Output is correct
28 Correct 772 ms 28372 KB Output is correct
29 Correct 774 ms 47568 KB Output is correct
30 Correct 763 ms 47576 KB Output is correct
31 Correct 139 ms 27488 KB Output is correct
32 Correct 637 ms 46428 KB Output is correct