Submission #890434

#	Time	Username	Problem	Language	Result	Execution time	Memory
890434		Minbaev	Sandwich (JOI16_sandwich)	C++17	0 / 100	1 ms	3420 KiB

sandwich

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N=1e5*4;
int ans = 0;

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}
vector<int>vis(N);
struct node{
	
	node *next[26];
	vector<int>v;
	node(){
		for(int i = 0; i < 26; i++)next[i] = nullptr;
	}
};

node *root = new node();

void add(string s,int ind){
	node *cur = root;
	
	for(int i = 0;i<s.size();i++){
		if(cur->next[s[i]-'A'] == nullptr)cur->next[s[i]-'A'] = new node();
		cur = cur->next[s[i]-'A'];
		cur->v.pb(ind);
	}
	
}

void check(string s){
	node *cur = root;
	for(int i = 0;i<s.size();i++){
		
		if(cur->next[s[i]-'A'] == nullptr)return;
		cur = cur->next[s[i]-'A'];
		if(s.size()-1==i)for(auto to:cur->v)vis[to]++;
		
	}
	
}
//------------------2---------------------------------
struct node1{
	
	node1 *next[26];
	vector<int>v;
	node1(){
		for(int i = 0; i < 26; i++)next[i] = nullptr;
	}
};

node1 *root1 = new node1();

void add1(string s,int ind){
	node1 *cur = root1;
	
	for(int i = 0;i<s.size();i++){
		if(cur->next[s[i]-'A'] == nullptr)cur->next[s[i]-'A'] = new node1();
		cur = cur->next[s[i]-'A'];
		cur->v.pb(ind);
	}
	
}

void check1(string s){
	node1 *cur = root1;
	for(int i = 0;i<s.size();i++){
		
		if(cur->next[s[i]-'A'] == nullptr)return;
		cur = cur->next[s[i]-'A'];
		if(s.size()-1==i)for(auto to:cur->v)vis[to]++;
		
		
	}
	
}

void solve(){
	int n,m,k;
	cin >> n >> m;
	
	string s[n];
	for(int i = 0; i < n; i++){
		cin >> s[i];
		add(s[i],i);
	}
	
	for(int i = 0; i < n; i++){
		reverse(all(s[i]));
		add1(s[i],i);
	}
	
	//~ check("AA");
	while(m--){
		string a,b;
		cin>> a>> b;
		for(int i = 0;i<n;i++)vis[i] = 0;
		check(a);
		reverse(all(b));
		check1(b);
		int cnt = 0;
		for(int i = 0;i<n;i++)if(vis[i]==2)cnt++;
		cout<<cnt<<"\n";
	}









}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int cnt=0;
	int tt=1;//cin>>tt;
	while(tt--)solve();

}

Compilation message (stderr)

sandwich.cpp: In function 'void add(std::string, long long int)':
sandwich.cpp:49:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0;i<s.size();i++){
      |                ~^~~~~~~~~
sandwich.cpp: In function 'void check(std::string)':
sandwich.cpp:59:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0;i<s.size();i++){
      |                ~^~~~~~~~~
sandwich.cpp:63:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   63 |   if(s.size()-1==i)for(auto to:cur->v)vis[to]++;
      |                ^
sandwich.cpp: In function 'void add1(std::string, long long int)':
sandwich.cpp:83:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i = 0;i<s.size();i++){
      |                ~^~~~~~~~~
sandwich.cpp: In function 'void check1(std::string)':
sandwich.cpp:93:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 0;i<s.size();i++){
      |                ~^~~~~~~~~
sandwich.cpp:97:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   97 |   if(s.size()-1==i)for(auto to:cur->v)vis[to]++;
      |                ^
sandwich.cpp: In function 'void solve()':
sandwich.cpp:105:10: warning: unused variable 'k' [-Wunused-variable]
  105 |  int n,m,k;
      |          ^
sandwich.cpp: In function 'int main()':
sandwich.cpp:147:6: warning: unused variable 'cnt' [-Wunused-variable]
  147 |  int cnt=0;
      |      ^~~

• Subtask 1: 0 / 35
• Subtask 2: 0 / 65