oj.uz

Submission #151039

# Submission time Handle Problem Language Result Execution time Memory
151039 2019-09-01T15:21:56 Z dongwon0427 HicCup (FXCUP4_hiccup) C++17
24 / 100
 116 ms 43660 KB 
#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++) {
        sum += len[child[idx][i]];
        mn = std::min(mn, sum/(i+1));
    }
    return mn;
}
int HicCup(std::string S) {
	int n = S.size();

	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");
        }
	}*/
	return dfs(1);;
}

Compilation message

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++) {
                 ~^~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 27 ms 24568 KB Output is correct
5 Correct 113 ms 43652 KB Output is correct
6 Correct 30 ms 27768 KB Output is correct
7 Correct 30 ms 27768 KB Output is correct
8 Correct 116 ms 43640 KB Output is correct
9 Correct 114 ms 43660 KB Output is correct
10 Correct 30 ms 27768 KB Output is correct
11 Correct 23 ms 23800 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 27 ms 24568 KB Output is correct
5 Correct 113 ms 43652 KB Output is correct
6 Correct 30 ms 27768 KB Output is correct
7 Correct 30 ms 27768 KB Output is correct
8 Correct 116 ms 43640 KB Output is correct
9 Correct 114 ms 43660 KB Output is correct
10 Correct 30 ms 27768 KB Output is correct
11 Correct 33 ms 29304 KB Output is correct
12 Correct 34 ms 30584 KB Output is correct
13 Correct 31 ms 28152 KB Output is correct
14 Correct 23 ms 23800 KB Output is correct
15 Correct 45 ms 39544 KB Output is correct
16 Incorrect 23 ms 23800 KB Output isn't correct
17 Halted 0 ms 0 KB -