oj.uz

Submission #419533

# Submission time Handle Problem Language Result Execution time Memory
419533 2021-06-07T08:43:56 Z mosiashvililuka Zagrade (COI17_zagrade) C++17
40 / 100
 3000 ms 61660 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14540 KB Output is correct
2 Correct 10 ms 14496 KB Output is correct
3 Correct 10 ms 14540 KB Output is correct
4 Correct 10 ms 14540 KB Output is correct
5 Correct 11 ms 14528 KB Output is correct
6 Correct 10 ms 14540 KB Output is correct
7 Correct 11 ms 14536 KB Output is correct
8 Correct 11 ms 14500 KB Output is correct
9 Correct 10 ms 14412 KB Output is correct
10 Correct 9 ms 14556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 52352 KB Output is correct
2 Correct 747 ms 58876 KB Output is correct
3 Correct 584 ms 52308 KB Output is correct
4 Correct 727 ms 57720 KB Output is correct
5 Correct 613 ms 52336 KB Output is correct
6 Correct 574 ms 52824 KB Output is correct
7 Correct 624 ms 52228 KB Output is correct
8 Correct 595 ms 52856 KB Output is correct
9 Correct 599 ms 52312 KB Output is correct
10 Correct 581 ms 61660 KB Output is correct
11 Correct 641 ms 57240 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14540 KB Output is correct
2 Correct 10 ms 14496 KB Output is correct
3 Correct 10 ms 14540 KB Output is correct
4 Correct 10 ms 14540 KB Output is correct
5 Correct 11 ms 14528 KB Output is correct
6 Correct 10 ms 14540 KB Output is correct
7 Correct 11 ms 14536 KB Output is correct
8 Correct 11 ms 14500 KB Output is correct
9 Correct 10 ms 14412 KB Output is correct
10 Correct 9 ms 14556 KB Output is correct
11 Correct 572 ms 52352 KB Output is correct
12 Correct 747 ms 58876 KB Output is correct
13 Correct 584 ms 52308 KB Output is correct
14 Correct 727 ms 57720 KB Output is correct
15 Correct 613 ms 52336 KB Output is correct
16 Correct 574 ms 52824 KB Output is correct
17 Correct 624 ms 52228 KB Output is correct
18 Correct 595 ms 52856 KB Output is correct
19 Correct 599 ms 52312 KB Output is correct
20 Correct 581 ms 61660 KB Output is correct
21 Correct 641 ms 57240 KB Output is correct
22 Execution timed out 3058 ms 37164 KB Time limit exceeded
23 Halted 0 ms 0 KB -