oj.uz

Submission #96600

# Submission time Handle Problem Language Result Execution time Memory
96600 2019-02-10T11:44:45 Z mraron Parametriziran (COCI19_parametriziran) C++14
88 / 110
 530 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);
}
//int c=0;
struct trie {
	vector<pair<int, trie*>> sub;
	//trie* sub[26];
	int cnt;
	trie() {
		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;
	string mm;
	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";
		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;
	string nemk;


	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);
		}

		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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2040 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2168 KB Output is correct
2 Correct 10 ms 2172 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2200 KB Output is correct
2 Correct 20 ms 2168 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3192 KB Output is correct
2 Correct 17 ms 2424 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3036 KB Output is correct
2 Correct 50 ms 4088 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 10996 KB Output is correct
2 Correct 21 ms 2424 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 21844 KB Output is correct
2 Correct 22 ms 2424 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 38776 KB Output is correct
2 Correct 258 ms 19192 KB Output is correct

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 530 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 391 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -