oj.uz

Submission #419532

# Submission time Handle Problem Language Result Execution time Memory
419532 2021-06-07T08:43:20 Z mosiashvililuka Zagrade (COI17_zagrade) C++14
40 / 100
 3000 ms 61560 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 12 ms 14540 KB Output is correct
2 Correct 10 ms 14540 KB Output is correct
3 Correct 10 ms 14540 KB Output is correct
4 Correct 13 ms 14540 KB Output is correct
5 Correct 12 ms 14540 KB Output is correct
6 Correct 11 ms 14432 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 11 ms 14512 KB Output is correct
9 Correct 10 ms 14412 KB Output is correct
10 Correct 9 ms 14524 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 52308 KB Output is correct
2 Correct 698 ms 58968 KB Output is correct
3 Correct 570 ms 52456 KB Output is correct
4 Correct 694 ms 57788 KB Output is correct
5 Correct 586 ms 52452 KB Output is correct
6 Correct 567 ms 52956 KB Output is correct
7 Correct 571 ms 52308 KB Output is correct
8 Correct 569 ms 52956 KB Output is correct
9 Correct 613 ms 52324 KB Output is correct
10 Correct 602 ms 61560 KB Output is correct
11 Correct 638 ms 57144 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14540 KB Output is correct
2 Correct 10 ms 14540 KB Output is correct
3 Correct 10 ms 14540 KB Output is correct
4 Correct 13 ms 14540 KB Output is correct
5 Correct 12 ms 14540 KB Output is correct
6 Correct 11 ms 14432 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 11 ms 14512 KB Output is correct
9 Correct 10 ms 14412 KB Output is correct
10 Correct 9 ms 14524 KB Output is correct
11 Correct 581 ms 52308 KB Output is correct
12 Correct 698 ms 58968 KB Output is correct
13 Correct 570 ms 52456 KB Output is correct
14 Correct 694 ms 57788 KB Output is correct
15 Correct 586 ms 52452 KB Output is correct
16 Correct 567 ms 52956 KB Output is correct
17 Correct 571 ms 52308 KB Output is correct
18 Correct 569 ms 52956 KB Output is correct
19 Correct 613 ms 52324 KB Output is correct
20 Correct 602 ms 61560 KB Output is correct
21 Correct 638 ms 57144 KB Output is correct
22 Execution timed out 3064 ms 41256 KB Time limit exceeded
23 Halted 0 ms 0 KB -