oj.uz

Submission #419531

# Submission time Handle Problem Language Result Execution time Memory
419531 2021-06-07T08:40:49 Z mosiashvililuka Zagrade (COI17_zagrade) C++14
10 / 100
 700 ms 58924 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],pas;
vector <int> v[300009];
int A[300009],Ai,Bi;
pair <int, int> B[300009];
vector <int> vv[300009];
int fx[300009];
string s;
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);
	}
}
int fun(){
	int 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;
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14412 KB Output is correct
2 Correct 10 ms 14460 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 11 ms 14428 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 12 ms 14464 KB Output is correct
7 Correct 11 ms 14436 KB Output is correct
8 Correct 11 ms 14412 KB Output is correct
9 Correct 11 ms 14412 KB Output is correct
10 Correct 10 ms 14440 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 47524 KB Output is correct
2 Correct 700 ms 55684 KB Output is correct
3 Correct 589 ms 51848 KB Output is correct
4 Correct 699 ms 55080 KB Output is correct
5 Correct 603 ms 51796 KB Output is correct
6 Correct 624 ms 51964 KB Output is correct
7 Correct 581 ms 51836 KB Output is correct
8 Correct 590 ms 52092 KB Output is correct
9 Correct 577 ms 51928 KB Output is correct
10 Correct 590 ms 58924 KB Output is correct
11 Incorrect 691 ms 54316 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14412 KB Output is correct
2 Correct 10 ms 14460 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 11 ms 14428 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 12 ms 14464 KB Output is correct
7 Correct 11 ms 14436 KB Output is correct
8 Correct 11 ms 14412 KB Output is correct
9 Correct 11 ms 14412 KB Output is correct
10 Correct 10 ms 14440 KB Output is correct
11 Correct 588 ms 47524 KB Output is correct
12 Correct 700 ms 55684 KB Output is correct
13 Correct 589 ms 51848 KB Output is correct
14 Correct 699 ms 55080 KB Output is correct
15 Correct 603 ms 51796 KB Output is correct
16 Correct 624 ms 51964 KB Output is correct
17 Correct 581 ms 51836 KB Output is correct
18 Correct 590 ms 52092 KB Output is correct
19 Correct 577 ms 51928 KB Output is correct
20 Correct 590 ms 58924 KB Output is correct
21 Incorrect 691 ms 54316 KB Output isn't correct