Submission #102345

#	Time	Username	Problem	Language	Result	Execution time	Memory
102345		JedrzejOlkowski	Dijamant (COI16_dijament)	C++14	13 / 100	302 ms	4656 KiB

dijament

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;
const int BS=40;
const int M=31;

int Przodek[N][BS];
int Kuzyn[N][BS];
int MaskaSasiedzi[BS];
int Kra[N][N];

unordered_map<string, int>IdWie;
int id=0;
vector<int>Sasiedzi;
string rep;

int Literka(char znak){
	if( (int)znak>=97 && (int)znak<=122 ) return 1;
	return 0;
}


int ZamienWejscie(){
	string slowo, aktu; int j, i;
	getline(cin, slowo); Sasiedzi.clear();
	for(i=0; i<(int)slowo.size(); i++){
		j=i; rep=slowo[i];
		while( Literka(slowo[j+1]) ){
			j++;
			rep+=slowo[j];
		}
		if( IdWie[rep]>0 ) return 0;
		break;
	}
	for(i=j+4; i<(int)slowo.size(); i++){
		if( slowo[i]==';' ) break;
		aktu=slowo[i]; j=i;
		while( Literka(slowo[j+1]) ){
			j++;
			aktu+=slowo[j];
		}
		if( IdWie[aktu]==0 ) return 0;
		Sasiedzi.push_back( IdWie[aktu] );
		i=j+1;
	}
	IdWie[rep]=++id;
	return 1;
}

int CzyDiament(int n){
	for(int i=0; i<BS; i++) MaskaSasiedzi[i]=0;
	for(int i=0; i<(int)Sasiedzi.size(); i++)	MaskaSasiedzi[ Sasiedzi[i]/M ]+= (1<<(Sasiedzi[i]%M));
	for(int i=0; i<(int)Sasiedzi.size(); i++){
		for(int j=0; j<BS; j++){
			if( (Kuzyn[ Sasiedzi[i] ][j]&MaskaSasiedzi[j])>0 ) return 0;
		}	
	}
	return 1;
}

void DodajKuzyna(int aktu){
	Kuzyn[id][ aktu/M ]+=(1<<(aktu%M));
	Kuzyn[aktu][ id/M ]+=(1<<(id%M));
}

int NiePrzodek(int v, int u){
	if( ( Przodek[v][ u/M ]&(1<<(u%M)) )>0 ) return 0;
	if( ( Przodek[u][ v/M ]&(1<<(v%M)) )>0 ) return 0;
	return 1;
}

void LiczPrzodkowKuzynow(int n){
	for(int i=0; i<(int)Sasiedzi.size(); i++){
		for(int j=0; j<BS; j++) Przodek[id][j]=( Przodek[ Sasiedzi[i] ][j] | Przodek[id][j] );
		Kra[ Sasiedzi[i] ][id]=1;
	}
	Przodek[ id ][ id/M ]+=(1<<(id%M));
	for(int i=1; i<=n; i++){
		if( NiePrzodek(i, id )==0 || i==id ) continue;
		for(int j=0; j<BS; j++){
			if( (Przodek[id][j]&Przodek[i][j])>0 ) DodajKuzyna(i);
		}
	}
}

int main (){
	int n, wejscie, d; string slowo;
	cin>>n;
	getline(cin, slowo);
	for(int i=1; i<=n; i++){
		wejscie=ZamienWejscie();
	//	cout << endl;
	//	cout << "I " << i << ": " << rep << endl;
		if( wejscie==0 ){
			cout<<"greska\n";
			continue;
		}
		d=CzyDiament(n);
		if( d==0 ){
			IdWie[rep]=0; id--;
			cout<<"greska\n";
			continue;
		}
	//	cout << "rep " << rep << ": " << id << endl;
		LiczPrzodkowKuzynow(n);
	//	cout << "kuzyni i przodkowe po " << endl;
	//	for(int j=1; j<=n; j++) cout<<"("<<j<<", "<<Przodek[j][0]<<"), ";
	//	cout << endl;
	//	for(int j=1; j<=n; j++) cout<<"("<<j<<", "<<Kuzyn[j][0]<<"), ";
	//	cout << endl;
			
		cout << "ok\n";
		//cout << i << "-" << wejscie << ": ";
		//for(int j=0; j<(int)Sasiedzi.size(); j++) cout << Sasiedzi[j] << " ";
		//cout << endl;
	}
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 29
• Subtask 4: 0 / 44