Submission #151047

#	Time	Username	Problem	Language	Result	Execution time	Memory
151047		dongwon0427	HicCup (FXCUP4_hiccup)	C++17	100 / 100	149 ms	43880 KiB

hiccup

#include "hiccup.h"
#include <stack>
#include <vector>

int par[1000005];
int fr[1000005];
int len[1000005];
std::vector<int> child[1000005];

int dfs(int idx) {

    int mn = 1e6;
    int sum = 0;
    for(int i=0;i<child[idx].size();i++) {
        mn = std::min(mn, dfs(child[idx][i]));
    }
    for(int i=0;i<child[idx].size();i++) {
        sum += len[child[idx][i]];
        mn = std::min(mn, sum/(i+1));
    }
    return mn;
}
int HicCup(std::string S) {
	int n = S.size();
	if(S[0] != 'H') return -1;

	std::stack<int> ST;
	ST.push(1);
	for(int i=0;i<n;i++) {
        if(S[i] == 'H') {
            par[i+2] = ST.top();
            ST.push(i+2);
        } else if(S[i] == 'C') {
            if(ST.top() == 1) return -1;
            fr[i] = ST.top();
            ST.pop();
        }
	}
	if(ST.size() != 1) return -1;

	for(int i=0;i<n;i++) {
        if(S[i] == 'C') {
            if(fr[i] == 0) return -1;
        }
	}

	for(int i=0;i<n;i++) {
        if(S[i] == 'C') {
            for(int j=i+1;j<n;j++) {
                if(S[j] != '!') break;
                len[fr[i]]++;
            }
        }
	}

	for(int i=0;i+1<n;i++) {
        if(S[i] == 'H') {
            if(S[i+1] == '!') return -1;
        }
	}

	for(int i=n-1;i>=0;i--) {
        if(S[i] == 'H') {
            child[par[i+2]].push_back(i+2);
        }
	}



	/*for(int i=0;i<n;i++) {
        if(S[i] == 'H') {
            printf("%d %d\n",i+2,len[i+2]);
        }
	}

	for(int i=1;i<=n+2;i++) {
        if(child[i].size()) {
            printf("%d ",i);
            for(int j : child[i]) printf("%d ",j);
            printf("\n");
        }
	}*/
	//HHC!!!HC!C!!!!!!
	return dfs(1);
}

Compilation message (stderr)

hiccup.cpp: In function 'int dfs(int)':
hiccup.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<child[idx].size();i++) {
                 ~^~~~~~~~~~~~~~~~~~
hiccup.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<child[idx].size();i++) {
                 ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 24 / 24
• Subtask 2: 76 / 76