oj.uz

Submission #151044

# Submission time Handle Problem Language Result Execution time Memory
151044 2019-09-01T15:28:33 Z dongwon0427 HicCup (FXCUP4_hiccup) C++17
24 / 100
 114 ms 42784 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();
	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");
        }
	}*/
	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 24 ms 23740 KB Output is correct
2 Correct 23 ms 23804 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 42648 KB Output is correct
6 Correct 30 ms 26744 KB Output is correct
7 Correct 30 ms 26744 KB Output is correct
8 Correct 114 ms 42716 KB Output is correct
9 Correct 113 ms 42784 KB Output is correct
10 Correct 30 ms 26744 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 24 ms 23740 KB Output is correct
2 Correct 23 ms 23804 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 42648 KB Output is correct
6 Correct 30 ms 26744 KB Output is correct
7 Correct 30 ms 26744 KB Output is correct
8 Correct 114 ms 42716 KB Output is correct
9 Correct 113 ms 42784 KB Output is correct
10 Correct 30 ms 26744 KB Output is correct
11 Correct 33 ms 28280 KB Output is correct
12 Correct 34 ms 29560 KB Output is correct
13 Correct 31 ms 27120 KB Output is correct
14 Correct 23 ms 23800 KB Output is correct
15 Correct 45 ms 38396 KB Output is correct
16 Correct 24 ms 23800 KB Output is correct
17 Correct 24 ms 23800 KB Output is correct
18 Correct 24 ms 24184 KB Output is correct
19 Correct 47 ms 39288 KB Output is correct
20 Incorrect 48 ms 39544 KB Output isn't correct
21 Halted 0 ms 0 KB -