oj.uz

Submission #96588

# Submission time Handle Problem Language Result Execution time Memory
96588 2019-02-10T11:21:23 Z mraron Parametriziran (COCI19_parametriziran) C++14
77 / 110
 1372 ms 66560 KB 
/*
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);
}

struct trie {
	map<int, trie*> sub;
	int cnt;
	trie() {
		cnt=0;
	}
};

void insert(trie *root, string& t){
	for(auto i:t) {
		if(root->sub.count(i-'a')==0) {
			root->sub[i-'a']=new trie();
		}
		root=root->sub[i-'a'];
	}
	
	root->cnt++;
}

int cnt(trie *root, string &t) {
	for(auto i:t) {
		if(root->sub.count(i-'a')==0) {
			return 0;
		}
		
		root=root->sub[i-'a'];
	}
	
	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) {
		string akt;
		cin>>akt;
		t[i]=akt;
		vector<int> nemk;
		for(int j=0;j<k;++j) {
			if(akt[j]!='?') nemk.push_back(j);
		}
		//for(auto i:nemk) cerr<<i<<" ";
		//cerr<<"NEMK\n";
		for(int j=0;j<(1<<sz(nemk));++j) {
			string mm;
			int mask=0;
			for(int l=0;l<sz(nemk);++l) {
				if((1<<l)&j) {
					mask+=2*hatv[nemk[l]];
					mm.push_back(akt[nemk[l]]);
				}else {
					mask+=1*hatv[nemk[l]];
				}
			}
			//cerr<<mask<<" ("<<j<<")"<<" -> "<<mm<<" insert\n";
			insert(tr[mask], mm);
		}
	}
	
	ll res=0;
	for(int i=0;i<n;++i) {
		vector<int> kk, nk;
		
		for(int j=0;j<k;++j) {
			if(t[i][j]!='?') {
				nk.push_back(j);
			}
			else kk.push_back(j);
		}
		
		for(int q=0;q<(1<<sz(nk));++q) {
			int mask_base=0;
			string nemk;
			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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2168 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2296 KB Output is correct
2 Correct 17 ms 2168 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2168 KB Output is correct
2 Correct 32 ms 2168 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3964 KB Output is correct
2 Correct 34 ms 2808 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 3576 KB Output is correct
2 Correct 77 ms 5624 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 17756 KB Output is correct
2 Correct 47 ms 2692 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 37044 KB Output is correct
2 Correct 48 ms 2680 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1372 ms 66280 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 481 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 414 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -