Submission #96598

#	Time	Username	Problem	Language	Result	Execution time	Memory
96598		mraron	Parametriziran (COCI19_parametriziran)	C++14	0 / 110	3041 ms	59224 KiB

Main

/*
ID: noszaly1
TASK: {TASK}
LANG: C++11               
*/

//Noszály Áron 11o Debreceni Fazekas Mihály Gimnázium

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}
int c=0;
struct trie {
	vector<pair<int, trie*>> sub;
	//trie* sub[26];
	short cnt;
	trie() {
		cerr<<"CREATED"<<c++<<"\n";
		
		cnt=0;
	}
};

void insert(trie *root, string& t){
	for(auto i:t) {
		trie* idx=0;
		for(auto j:root->sub) {
			if(j.first==i-'a') {
				idx=j.second;
			}
		}
		
		if(idx==0) {
			root->sub.push_back({i-'a', new trie()});
			idx=root->sub.back().second;
		}
		
		root=idx;
	}
	
	root->cnt++;
}

int cnt(trie *root, string &t) {
	for(auto i:t) {
		trie* idx=0;
		for(auto j:root->sub) {
			if(j.first==i-'a') {
				idx=j.second;
			}
		}
		
		if(idx==0) {
			return 0;
		}
		
		root=idx;
	}
	
	return root->cnt;
}

int hatv[10];
trie *tr[3000];
string t[50001];
int main() {
	IO;
	hatv[0]=1;
	for(int i=1;i<10;++i) hatv[i]=hatv[i-1]*3;
	for(int i=0;i<3000;++i) tr[i]=new trie();
	
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;++i) {
		cin>>t[i];
		vector<int> nemk;
		for(int j=0;j<k;++j) {
			if(t[i][j]!='?') nemk.push_back(j);
		}
		//for(auto i:nemk) cerr<<i<<" ";
		//cerr<<"NEMK\n";
		string mm;
		for(int j=0;j<(1<<sz(nemk));++j) {
			mm.clear();
			int mask=0;
			for(int l=0;l<sz(nemk);++l) {
				if((1<<l)&j) {
					mask+=2*hatv[nemk[l]];
					mm.push_back(t[i][nemk[l]]);
				}else {
					mask+=1*hatv[nemk[l]];
				}
			}
			//cerr<<mask<<" ("<<j<<")"<<" -> "<<mm<<" insert\n";
			insert(tr[mask], mm);
		}
	}
	
	ll res=0;
	vector<int> kk, nk;

	for(int i=0;i<n;++i) {
		kk.clear();
		nk.clear();
		for(int j=0;j<k;++j) {
			if(t[i][j]!='?') {
				nk.push_back(j);
			}
			else kk.push_back(j);
		}

		string nemk;
		for(int q=0;q<(1<<sz(nk));++q) {
			nemk.clear();
			int mask_base=0;
			for(int l=0;l<sz(nk);++l) {
				if((1<<l)&q) {
					mask_base+=hatv[nk[l]]*2;
					nemk+=t[i][nk[l]];
				}else {
				
				}
			}
			
			for(int j=0;j<(1<<sz(kk));++j) {
				int mask=mask_base;
				for(int l=0;l<sz(kk);++l) {
					if((1<<l)&j) {
						mask+=hatv[kk[l]];
					}	
				}
				
				//cerr<<mask<<" -> "<<nemk<<" CNT\n";
				res+=cnt(tr[mask], nemk);
			}
		}
	}
	assert((res-n)%2==0);
	cout<<(res-n)/2<<"\n";
	
	
	return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11