Submission #102354

#	Time	Username	Problem	Language	Result	Execution time	Memory
102354		JedrzejOlkowski	Dijamant (COI16_dijament)	C++14	100 / 100	464 ms	9916 KiB

dijament

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

const int N=2000+10;
const int BS=50;
const int M=31;

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

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 CzyPrzodek(int v, int u){
	if( ( Przodek[v][ u/M ]&(1<<(u%M)) )>0 ) return 1;
	if( ( Przodek[u][ v/M ]&(1<<(v%M)) )>0 ) return 1;
	return 0;
}

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( CzyPrzodek(i, id) || i==id ) continue;
		for(int j=0; j<BS; j++){
			if( (Przodek[id][j]&Przodek[i][j])>0 ){
				DodajKuzyna(i);
				break;
			}
		}
	}
}

int main (){
	int n, wejscie, d; string slowo;
	cin>>n;
	getline(cin, slowo);
	for(int i=1; i<=n; i++){
		wejscie=ZamienWejscie();
		if( wejscie==0 ){
			cout<<"greska\n";
			continue;
		}
		d=CzyDiament(n);
		if( d==0 ){
			IdWie[rep]=0; id--;
			cout<<"greska\n";
			continue;
		}
		LiczPrzodkowKuzynow(n);
		cout << "ok\n";
	}
	return 0;
}

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