oj.uz

Submission #419544

# Submission time Handle Problem Language Result Execution time Memory
419544 2021-06-07T09:11:05 Z mosiashvililuka Zagrade (COI17_zagrade) C++17
40 / 100
 3000 ms 54588 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];
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;
	}
	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;
	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:175:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |  scanf("%d\n",&a);
      |  ~~~~~^~~~~~~~~~~
zagrade.cpp:185:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |   if(i!=a-1) scanf("%d %d\n",&c,&d); else scanf("%d %d",&c,&d);
      |              ~~~~~^~~~~~~~~~~~~~~~~
zagrade.cpp:185:48: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |   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 11 ms 14412 KB Output is correct
2 Correct 10 ms 14500 KB Output is correct
3 Correct 10 ms 14412 KB Output is correct
4 Correct 10 ms 14424 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 11 ms 14412 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 12 ms 14412 KB Output is correct
9 Correct 10 ms 14508 KB Output is correct
10 Correct 9 ms 14412 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 47596 KB Output is correct
2 Correct 747 ms 51520 KB Output is correct
3 Correct 631 ms 47512 KB Output is correct
4 Correct 711 ms 50784 KB Output is correct
5 Correct 639 ms 47592 KB Output is correct
6 Correct 607 ms 47808 KB Output is correct
7 Correct 602 ms 47512 KB Output is correct
8 Correct 579 ms 47812 KB Output is correct
9 Correct 589 ms 47588 KB Output is correct
10 Correct 607 ms 54588 KB Output is correct
11 Correct 680 ms 50216 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 10 ms 14500 KB Output is correct
3 Correct 10 ms 14412 KB Output is correct
4 Correct 10 ms 14424 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 11 ms 14412 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 12 ms 14412 KB Output is correct
9 Correct 10 ms 14508 KB Output is correct
10 Correct 9 ms 14412 KB Output is correct
11 Correct 642 ms 47596 KB Output is correct
12 Correct 747 ms 51520 KB Output is correct
13 Correct 631 ms 47512 KB Output is correct
14 Correct 711 ms 50784 KB Output is correct
15 Correct 639 ms 47592 KB Output is correct
16 Correct 607 ms 47808 KB Output is correct
17 Correct 602 ms 47512 KB Output is correct
18 Correct 579 ms 47812 KB Output is correct
19 Correct 589 ms 47588 KB Output is correct
20 Correct 607 ms 54588 KB Output is correct
21 Correct 680 ms 50216 KB Output is correct
22 Execution timed out 3066 ms 30092 KB Time limit exceeded
23 Halted 0 ms 0 KB -