oj.uz

Submission #80275

# Submission time Handle Problem Language Result Execution time Memory
80275 2018-10-19T17:45:11 Z thiago4532 Lozinke (COCI17_lozinke) C++17
0 / 100
 34 ms 16368 KB 
#include <bits/stdc++.h>
#define gc getchar
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define rep2(i, a, b) for(int i=a;i>=b;--i)
#define wipe(a, b) memset(a, b, sizeof a);
#define pb push_back
#define ff first
#define ss second

using namespace std;
typedef pair<int, int> pii;

inline int scan(){
	int n=0, x=gc(), s=1;
	for(;x<'0'||x>'9';x=gc()) if(x=='-') s=-1;
	for(;x>='0'&&x<='9';x=gc()) n = 10*n + x - '0';
	return n*s;
}

int gcd(int a, int b){
	return (b?gcd(b, a%b):a);
}

struct node{
	node *son[26];
	int end, marca;
	node(){
		end = 0;
		marca = 0;
		for(int i=0;i<26;i++)
			son[i] = nullptr;
	}
};

node *root;

inline void add(string str){
	node *x = root;

	for(auto c : str){
		if(x->son[c-'a'] == nullptr) x->son[c-'a'] = new node();
		x = x->son[c-'a'];
	}
	x->end++;
}

int search(string str, int marca){
	node *x = root;
	int ans=0;

	for(auto c : str){
		if(!x->son[c-'a']) break;
		x = x->son[c-'a'];
		if(x->end > 0 && x->marca != marca) ans += x->end, x->marca = marca;
	}
	return ans;
}

int main(){
	//ios::sync_with_stdio(false), cin.tie(0);
	root = new node;
	int n;
	cin >> n;
	vector<string> str;
	for(int i=1;i<=n;i++){
		string x;
		cin >> x;
		str.push_back(x);
	}

	sort(str.begin(), str.end(), [](string const& a, string const& b){
		return a.size() < b.size();
	});

	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<(int)str[i].size();j++){
			int x = search(str[i].substr(j), i);
			//cout << "Valor da palavra " << str[i] << ": " << x << "\n";
			ans += x;
		}
		//cout << "Adicionando palavra " << str[i] << "\n";
		add(str[i]);
	}

	int qtd=1;
	string atual = str[0];
	for(int i=1;i<(int)str.size();i++){
		if(str[i] == atual) ++qtd;
		else{
			ans += ((qtd*(qtd-1))/2);
			qtd=1;
		}
	}
	ans += ((qtd*(qtd-1)));
	cout << ans << "\n";
	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Incorrect 2 ms 508 KB Output isn't correct
4 Incorrect 2 ms 636 KB Output isn't correct
5 Incorrect 3 ms 1036 KB Output isn't correct
6 Incorrect 4 ms 1176 KB Output isn't correct
7 Incorrect 5 ms 1832 KB Output isn't correct
8 Incorrect 5 ms 2256 KB Output isn't correct
9 Incorrect 12 ms 3912 KB Output isn't correct
10 Incorrect 17 ms 8008 KB Output isn't correct
11 Incorrect 17 ms 8008 KB Output isn't correct
12 Incorrect 32 ms 15048 KB Output isn't correct
13 Incorrect 23 ms 15048 KB Output isn't correct
14 Incorrect 29 ms 15596 KB Output isn't correct
15 Incorrect 34 ms 16368 KB Output isn't correct
16 Incorrect 20 ms 16368 KB Output isn't correct
17 Incorrect 19 ms 16368 KB Output isn't correct
18 Incorrect 17 ms 16368 KB Output isn't correct
19 Incorrect 29 ms 16368 KB Output isn't correct
20 Incorrect 28 ms 16368 KB Output isn't correct