Submission #796170

#	Time	Username	Problem	Language	Result	Execution time	Memory
796170		amirhoseinfar1385	Homework (CEOI22_homework)	C++17	100 / 100	166 ms	149436 KiB

Main

#include<bits/stdc++.h>
using namespace std;
string s;
struct dade{
	int c,r,n,ted,tl,tr;
	dade(){
		c=r=n=-1;
		tl=tr=ted=0;
	}
};

const int maxm=7000000+10;
int mid[maxm],sz;
vector<dade>allt;

void cals(){
	vector<int>v;
	for(int i=0;i<sz;i++){
		if(s[i]=='('){
			v.push_back(i);
			continue;
		}
		if(s[i]==')'){
			v.pop_back();
			continue;
		}
		if(s[i]==','){
			mid[v.back()]=i;
			continue;
		}
	}	
}
dade d;

int createtree(int l,int r){
	allt.push_back(d);
	int w=(int)allt.size()-1;
	if(l==r){
		allt[w].n=0;
		return w;
	}
	if(s[l+1]=='a'){
		allt[w].n=2;
	}
	else{
		allt[w].n=1;
	}
	allt[w].c=createtree(l+4,mid[l+3]-1);
	allt[w].r=createtree(mid[l+3]+1,r-1);
	return w;
}

void solve(int i){
	if(allt[i].n==0){
		allt[i].ted=1;
		allt[i].tl=allt[i].tr=1;
		return ;
	}
	int c=allt[i].c,r=allt[i].r;
	solve(c);
	solve(r);
	allt[i].ted=allt[c].ted+allt[r].ted;
	if(allt[i].n==1){
		allt[i].tl=min(allt[c].tl,allt[r].tl);
		allt[i].tr=allt[i].ted-(allt[r].ted-allt[r].tr)-(allt[c].ted-allt[c].tr)-1;
	}
	else{
		allt[i].tr=allt[i].ted-min(allt[c].ted-allt[c].tr,allt[r].ted-allt[r].tr);
		allt[i].tl=allt[r].tl+allt[c].tl;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	sz=(int)s.size();
	cals();
	createtree(0,sz-1);
	solve(0);
	int res=allt[0].tr-allt[0].tl+1;
	cout<<res<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34