제출 #1116332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116332		nikolashami	Homework (CEOI22_homework)	C++17	100 / 100	158 ms	161268 KiB

Main

#include <bits/stdc++.h>
using namespace std;

//?->0
//min->1
//max->2

const int N=4e6+2;
int id=1,n;
string s;

struct range{
	int l,r,sz;
}dp[N];

struct{
	int tp=0,idx;
}lc[N],rc[N];

int r(int i,int node){
	bool desno=0;
	while(i<n){
		if(s[i]=='?'){
			if(!desno){
				lc[node].tp=0;
				lc[node].idx=++id;
				desno=1;
			}else{
				rc[node].tp=0;
				rc[node].idx=++id;
			}
		}
		else if(s[i]=='('){
			if(!desno){
				lc[node].tp=(s[i-1]=='x'?2:1);
				lc[node].idx=++id;
				i=r(i+1,id);
				desno=1;
			}else{
				rc[node].tp=(s[i-1]=='x'?2:1);
				rc[node].idx=++id;
				i=r(i+1,id);
			}
			continue;
		}
		else if(s[i]==')')
			return i+1;
		++i;
	}
	return n-1;
}

void dfs(int node,int stanje){
	range levo,desno;
	if(lc[node].tp){
		dfs(lc[node].idx,lc[node].tp);
		levo=dp[lc[node].idx];
	}else{
		levo.l=levo.r=0;
		levo.sz=1;
	}
	if(rc[node].tp){
		dfs(rc[node].idx,rc[node].tp);
		desno=dp[rc[node].idx];
	}else{
		desno.l=desno.r=0;
		desno.sz=1;
	}
	dp[node].sz=levo.sz+desno.sz;
	if(stanje==1){	
		dp[node].l=min(levo.l,desno.l);
		dp[node].r=levo.r+desno.r;
	}else{
		dp[node].l=levo.l+desno.l+1;
		dp[node].r=max(levo.r+desno.sz,desno.r+levo.sz);
	}
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>s;
	n=s.size();

	r(4,1);
	dfs(1,(s[2]=='x'?2:1));

	cout<<dp[1].r-dp[1].l+1;
}

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