제출 #1040418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1040418		shiroihana	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	209 ms	277844 KiB

selling_rna

#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;
		}
	};
	
	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 (string Q, int l, int r) {
		if (l > r) return 0;
		reverse(Q.begin(), Q.end());
		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[(int)'A'] = 0;
	NUM[(int)'C'] = 1;
	NUM[(int)'G'] = 2;
	NUM[(int)'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();
}

컴파일 시 표준 에러 (stderr) 메시지

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: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40