oj.uz

Submission #96602

# Submission time Handle Problem Language Result Execution time Memory
96602 2019-02-10T11:47:59 Z mraron Parametriziran (COCI19_parametriziran) C++14
88 / 110
 603 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<char, trie*>> sub;
	int cnt;
	trie() {
	//	cerr<<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) {
				idx=j.second;
			}
		}
		
		if(idx==0) {
			root->sub.push_back({i, 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) {
				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 13 ms 2168 KB Output is correct
2 Correct 11 ms 2044 KB Output is correct

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3164 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 33 ms 2936 KB Output is correct
2 Correct 35 ms 4216 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 10956 KB Output is correct
2 Correct 23 ms 2424 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 21928 KB Output is correct
2 Correct 30 ms 2424 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 39008 KB Output is correct
2 Correct 320 ms 19128 KB Output is correct

Subtask #9
0 / 11.0

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