Submission #837676

#	Time	Username	Problem	Language	Result	Execution time	Memory
837676		MohamedAhmed04	Homework (CEOI22_homework)	C++14	100 / 100	125 ms	145364 KiB

Main

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 4e6 + 10 ;

string s ;

int sz[MAX] , mark[MAX] ;
int L[MAX] , R[MAX] ;
int Lchild[MAX] , Rchild[MAX] ;

int val[MAX] ;

void dfs(int node)
{
	if(mark[node])
	{
		sz[node] = 1 ;
		L[node] = R[node] = 1 ;
		return ;
	}
	int x = Lchild[node] , y = Rchild[node] ;
	dfs(x) , dfs(y) ;
	sz[node] = sz[x] + sz[y] ;
	if(val[node]) //Max
		L[node] = L[x] + L[y] , R[node] = max(sz[x] + R[y] , sz[y] + R[x]) ;
	else
		L[node] = min(L[x] , L[y]) , R[node] = R[x] + R[y] - 1 ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>s ;
	stack<int>st ;
	int cur = 0 ;
	for(int i = 0 ; i < s.size() ; ++i)
	{
		if(s[i] == '(')
		{
			++cur ;
			if(st.size())
			{
				if(!Lchild[st.top()])
					Lchild[st.top()] = cur ;
				else
					Rchild[st.top()] = cur ;
			}
			st.push(cur) ;
			val[cur] = (s[i-1] == 'x') ; //Max
		}
		else if(s[i] == ')')
			st.pop() ;
		else if(s[i] == '?')
		{
			++cur ;
			mark[cur] = 1 ;
			if(!Lchild[st.top()])
				Lchild[st.top()] = cur ;
			else
				Rchild[st.top()] = cur ;
		}
	}
	dfs(1) ;
	return cout<<R[1] - L[1] + 1<<"\n" , 0 ;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0 ; i < s.size() ; ++i)
      |                  ~~^~~~~~~~~~

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