oj.uz

답안 #1040412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1040412 2024-08-01T03:39:29 Z shiroihana Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 139 ms 195028 KB 
#include <bits/stdc++.h>
using namespace std;

int cl () {
	cerr << "Time used: " << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
	return 0;
}

const int N = (int)1e5;
const char CHAR[4] = {'A', 'C', 'G', 'U'};
int NUM[256];

int n, m;

string s[N + 1];

struct TrieP {
	struct Node {
		Node *child[4];
		int l, r, exist;
		Node () : l(N + 1), r(0), exist(0) {
			for (int t(0); t < 4; ++t) child[t] = NULL;
		}
	};
	
	Node *root;
	TrieP () {
		root = new Node();
	}
	
	void Add (const string &x, int id) {
		Node *p = root;
		for (char f: x) {
			int c = NUM[(int)f];
			if (p -> child[c] == NULL) p -> child[c] = new Node();
			p = p -> child[c];
			p -> l = min(p -> l, id);
			p -> r = max(p -> r, id);
		}
		++(p -> exist);
	}
	
	pair <int, int> getLR (const string &P) {
		Node *p = root;
		for (char f: P) {
			int c = NUM[(int)f];
			if (p -> child[c] == NULL) return make_pair(N + 1, 0);
			p = p -> child[c];
		}
		return make_pair(p -> l, p -> r);
	}

	string curString = "";
	int curI = 0;
	
	void dfs (const Node *p) {
		for (int t(0); t < 4; ++t) if (p -> child[t] != NULL) {
			curString += CHAR[t];
			for (int i(0); i < p -> child[t] -> exist; ++i) {
				s[++curI] = curString;
			}
			dfs(p -> child[t]);
			curString.pop_back();
		}
	}
} tree1;

void init () {
	TrieP list;
	cin >> n >> m; string x;
	for (int i(1); i <= n; ++i) {
		cin >> x;
		list.Add(x, -1);
	}
	list.dfs(list.root);
}

struct TrieQ {
	struct Node {
		Node *child[4];
		vector <int> id;
		Node () {
			for (int t(0); t < 4; ++t) child[t] = NULL;
			id.clear();
		}
	};
	
	Node *root;
	TrieQ () {
		root = new Node();
	}
	
	void Add (string x, int i) {
		reverse(x.begin(), x.end());
		Node *p = root;
		for (char f: x) {
			int c = NUM[(int)f];
			if (p -> child[c] == NULL) p -> child[c] = new Node();
			p = p -> child[c];
			(p -> id).push_back(i);
		}
	}
	
	int getCount (const string &Q, int l, int r) {
		if (l > r) return 0;
		Node *p = root;
		for (char f: Q) {
			int c = NUM[(int)f];
			if (p -> child[c] == NULL) return 0;
			p = p -> child[c];
		}
		int lo = lower_bound((p -> id).begin(), (p -> id).end(), l) - (p -> id).begin();
		int up = upper_bound((p -> id).begin(), (p -> id).end(), r) - (p -> id).begin();
		return up - lo;
	}
} tree2;

void prep () {
	for (int i(1); i <= n; ++i) {
		tree1.Add(s[i], i);
		tree2.Add(s[i], i);
	}
}

int main () {
	#define PHILE "base"
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if (fopen(PHILE".inp", "r")) {
		freopen(PHILE".inp", "r", stdin); freopen(PHILE".out", "w", stdout);
	}
	
	NUM['A'] = 0;
	NUM['C'] = 1;
	NUM['G'] = 2;
	NUM['U'] = 3;

	init();
	prep();
	
	string P, Q;
	while (m--) {
		cin >> P >> Q;
		pair <int, int> LR = tree1.getLR(P);
		cout << tree2.getCount(Q, LR.first, LR.second) << '\n';
	}

	return cl();
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:129:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   freopen(PHILE".inp", "r", stdin); freopen(PHILE".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:129:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   freopen(PHILE".inp", "r", stdin); freopen(PHILE".out", "w", stdout);
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 3416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 139 ms 195028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 4824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 3416 KB Output isn't correct
2 Halted 0 ms 0 KB -