Submission #321198

#	Time	Username	Problem	Language	Result	Execution time	Memory
321198		colazcy	Lozinke (COCI17_lozinke)	C++17	100 / 100	42 ms	8800 KiB

lozinke

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
map<int,int> mp;
namespace ac{
	constexpr int maxnode = 2e5 + 100,sigmasiz = 26;
	int ch[maxnode][sigmasiz],val[maxnode],fail[maxnode],tot;
	inline int idx(char c){return c - 'a';}
	inline void insert(const string &str){
		int u = 0;
		for(auto x : str){
			int c = idx(x);
			if(!ch[u][c])ch[u][c] = ++tot;
			u = ch[u][c];
		}
		val[u]++;
	}
	inline void build(){
		queue<int> q;
		for(int i = 0;i < sigmasiz;i++)
			if(ch[0][i])q.push(ch[0][i]);
		while(!q.empty()){
			int u = q.front();q.pop();
			for(int i = 0;i < sigmasiz;i++)
				if(ch[u][i])fail[ch[u][i]] = ch[fail[u]][i],q.push(ch[u][i]);
				else ch[u][i] = ch[fail[u]][i];
		}
	}
	inline int query(const string &str){
		mp.clear();
		int u = 0;
		for(auto x : str){
			int c = idx(x);
			u = ch[u][c];
			for(int j = u;j;j = fail[j])
				if(val[j])mp[j] = val[j];
		}
		int res = 0;
		for(auto it : mp)res += it.second;
		return res;
	}
}
int n;
char tmp[32];
vector<string> vec;
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
		scanf("%s",tmp),vec.push_back(string(tmp));
	for(auto x : vec)ac::insert(x);
	ac::build();
	int ans = 0;
	for(auto x : vec)ans += ac::query(x);
	printf("%d\n",ans - n);
	return 0;
}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
lozinke.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%s",tmp),vec.push_back(string(tmp));
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100