oj.uz

답안 #57179

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57179 2018-07-14T08:31:21 Z 김세빈(#1653) Selling RNA Strands (JOI16_selling_rna) C++11
35 / 100
 1500 ms 178592 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

struct trie_node{
	vector <int> V;
	int C[4];
};

struct trie{
	trie_node T[2020202];
	int L[2020202], R[2020202];
	int tp;
	
	trie() { tp = 1; }
	
	void insert(int p, int i, int* k)
	{
		if(*k == -1){
			T[p].V.push_back(i);
			return;
		}
		else{
			if(!T[p].C[*k]) T[p].C[*k] = ++tp;
			insert(T[p].C[*k], i, k + 1);
		}
	}
	
	void dfs(int* A, int p, int& cnt)
	{
		int i;
		L[p] = cnt + 1;
		for(auto t: T[p].V) A[t] = ++cnt;
		for(i=0;i<4;i++){
			if(T[p].C[i]) dfs(A, T[p].C[i], cnt);
		}
		R[p] = cnt;
	}
	
	pii find(int p, int* k)
	{
		if(!p) return pii(-1, -1);
		if(*k == -1) return pii(L[p], R[p]);
		else return find(T[p].C[*k], k + 1);
	}
};

trie P, Q;
int A[101010], B[101010], S[101010];
char str[101010];
int n, m;

int get_sum(int l, int r, int x, int y)
{
	int i, ret = 0;
	
	for(i=0;i<n;i++){
		if(l <= A[i] && A[i] <= r && x <= B[i] && B[i] <= y) ret ++;
	}
	
	return ret;
}

int main()
{
	int i, j, l, r, x, y;
	pii p;
	
	scanf("%d%d", &n, &m);
	
	for(i=0;i<n;i++){
		scanf("%s", str);
		
		for(j=0;str[j];j++){
			if(str[j] == 'A') S[j] = 0;
			else if(str[j] == 'C') S[j] = 1;
			else if(str[j] == 'G') S[j] = 2;
			else S[j] = 3;
		}
		S[j] = -1;
		P.insert(1, i, S);
		
		reverse(S, S+j);
		Q.insert(1, i, S);
	}
	
	int cnt = 0;
	P.dfs(A, 1, cnt);
	cnt = 0;
	Q.dfs(B, 1, cnt);
	
	for(;m--;){
		scanf("%s", str);
		
		for(j=0;str[j];j++){
			if(str[j] == 'A') S[j] = 0;
			else if(str[j] == 'C') S[j] = 1;
			else if(str[j] == 'G') S[j] = 2;
			else S[j] = 3;
		}
		
		S[j] = -1;
		p = P.find(1, S);
		l = p.first; r = p.second;
		
		scanf("%s", str);
		
		for(j=0;str[j];j++){
			if(str[j] == 'A') S[j] = 0;
			else if(str[j] == 'C') S[j] = 1;
			else if(str[j] == 'G') S[j] = 2;
			else S[j] = 3;
		}
		reverse(S, S+j);
		
		S[j] = -1;
		p = Q.find(1, S);
		x = p.first; y = p.second;
		
		if(l == -1 || x == -1) printf("0\n"); 
		else printf("%d\n", get_sum(l, r, x, y));
	}
	
	return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", str);
   ~~~~~^~~~~~~~~~~
selling_rna.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", str);
   ~~~~~^~~~~~~~~~~
selling_rna.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", str);
   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 158544 KB Output is correct
2 Correct 170 ms 158564 KB Output is correct
3 Correct 159 ms 158776 KB Output is correct
4 Correct 162 ms 158776 KB Output is correct
5 Correct 165 ms 158776 KB Output is correct
6 Correct 166 ms 158776 KB Output is correct
7 Correct 159 ms 158776 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 359 ms 174560 KB Output is correct
2 Correct 493 ms 174560 KB Output is correct
3 Correct 417 ms 174560 KB Output is correct
4 Correct 469 ms 174560 KB Output is correct
5 Correct 505 ms 178332 KB Output is correct
6 Correct 490 ms 178592 KB Output is correct
7 Correct 261 ms 178592 KB Output is correct
8 Correct 467 ms 178592 KB Output is correct
9 Correct 430 ms 178592 KB Output is correct
10 Correct 311 ms 178592 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1597 ms 178592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 158544 KB Output is correct
2 Correct 170 ms 158564 KB Output is correct
3 Correct 159 ms 158776 KB Output is correct
4 Correct 162 ms 158776 KB Output is correct
5 Correct 165 ms 158776 KB Output is correct
6 Correct 166 ms 158776 KB Output is correct
7 Correct 159 ms 158776 KB Output is correct
8 Correct 359 ms 174560 KB Output is correct
9 Correct 493 ms 174560 KB Output is correct
10 Correct 417 ms 174560 KB Output is correct
11 Correct 469 ms 174560 KB Output is correct
12 Correct 505 ms 178332 KB Output is correct
13 Correct 490 ms 178592 KB Output is correct
14 Correct 261 ms 178592 KB Output is correct
15 Correct 467 ms 178592 KB Output is correct
16 Correct 430 ms 178592 KB Output is correct
17 Correct 311 ms 178592 KB Output is correct
18 Execution timed out 1597 ms 178592 KB Time limit exceeded
19 Halted 0 ms 0 KB -