oj.uz

Submission #613316

# Submission time Handle Problem Language Result Execution time Memory
613316 2022-07-30T04:30:52 Z czhang2718 HicCup (FXCUP4_hiccup) C++17
24 / 100
 76 ms 34868 KB 
// #include "hiccup.h"
using namespace std;
#include "bits/stdc++.h"

const int N=1e6+1;
vector<int> adj[N];
int cnt[N];
int X, nodes, ans;
bool bad;

void dfs(int x, int &c){
	c+=cnt[x];
	if(x) nodes++, ans=min(ans, c/nodes);
	// if(X==2) cout << x << " c " << c << "\n";
	for(int i=adj[x].size()-1; i>=0; i--){
		int k=adj[x][i];
		dfs(k, c);
	}
}

int HicCup(std::string S) {
	int n = S.size();
	ans=1e9;
	S='-'+S;
	stack<int> par;
	par.push(0);
	int prv=-1;
	for(int i=1; i<=n; i++){
		if(S[i]=='!'){
			if(prv==-1) return -1;
			cnt[prv]++;
			continue;
		}
		if(S[i]=='C'){
			if(par.size()<2) return -1;
			int p=par.top(); par.pop();
			prv=p;
			adj[par.top()].push_back(p);
		}
		else{
			par.push(i);
		}
	}
	// for(int i=0; i<=n; i++){
	// 	if(cnt[i]) cout << "cnt[" << i << "] " << cnt[i] << "\n";
	// }
	if(par.size()!=1) return -1;

	int c=0;
	dfs(0, c);
	return ans;
}

// int main(){
// 	string s;
// 	cin >> s;
// 	cout << HicCup(s);
// }

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23764 KB Output is correct
2 Correct 17 ms 23764 KB Output is correct
3 Correct 15 ms 23800 KB Output is correct
4 Correct 26 ms 24148 KB Output is correct
5 Correct 75 ms 34820 KB Output is correct
6 Correct 23 ms 27624 KB Output is correct
7 Correct 26 ms 27656 KB Output is correct
8 Correct 76 ms 34800 KB Output is correct
9 Correct 66 ms 34868 KB Output is correct
10 Correct 25 ms 27612 KB Output is correct
11 Correct 16 ms 23744 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23764 KB Output is correct
2 Correct 17 ms 23764 KB Output is correct
3 Correct 15 ms 23800 KB Output is correct
4 Correct 26 ms 24148 KB Output is correct
5 Correct 75 ms 34820 KB Output is correct
6 Correct 23 ms 27624 KB Output is correct
7 Correct 26 ms 27656 KB Output is correct
8 Correct 76 ms 34800 KB Output is correct
9 Correct 66 ms 34868 KB Output is correct
10 Correct 25 ms 27612 KB Output is correct
11 Correct 16 ms 23744 KB Output is correct
12 Correct 26 ms 28352 KB Output is correct
13 Correct 30 ms 28388 KB Output is correct
14 Correct 21 ms 27604 KB Output is correct
15 Correct 12 ms 23684 KB Output is correct
16 Incorrect 29 ms 30656 KB Output isn't correct
17 Halted 0 ms 0 KB -